Matematické Fórum

marros11 · 23. 03. 2010 19:44

Ahoj,

muzete mi pomoct s resenim prikladu:

Navrhnete DKA pro jazyk L nad abecedou {0, 1} obsahující práve ta slova, kde se alespon
trikrát vyskytuje podslovo 000. Výskyty podslov se mohou prekrývat, takže do jazyka L patrí
napríklad slovo 00000.
Poznámka: Soucástí rešení by melo být i zduvodnení toho, že daný DKA skutecne prijímá
výše popsaný jazyk.

Dekuji za radu.

Kondr · 24. 03. 2010 01:48

Stav musí obsahovat informaci o tom, kolik podslov 000 jsme našli (0,1,2,3a víc), v prvních 3 případech navíc i informaci o tom, čím aktuálně načtený řetězec končí (1,10,00). To nám dává 3*3+1 stavů, přechodová funkce se nechá snadno sestrojit.

marros11

↑ Kondr:

Pokusil jsem se podle navodu sestrojit DKA, viz obr.

Narazil jsem ale s problemem jak vyresit aby DKA prijimal i 00000. Muzete mi pls poradit jak na to?

Dekuji.

Vypis prechodovych funkci:

0 1
***********
-> q1 q2 q1
q2 q3 q1
q3 q4 q1
q4 q5 q4
q6 q7 q4
q7 q8 q7
q8 q9 q7
q9 q10 q7
<-q10 q10 q10

Kondr · 25. 03. 2010 18:54

No chce to upravit přechody z q3 a q6

0 1
***********
-> q1 q2 q1 //0 slov, konci na 1
q2 q3 q1 //0 slov, konci na 10
q3 q6 q1 //0 slov, konci na 00
q4 q5 q4 //1 slov, konci na 1
q5 q6 q5 //1 slov, konci na 10
q6 q9 q4 //1 slov, konci na 00
q7 q8 q7 //2 slov, konci na 1
q8 q9 q7 //2 slov, konci na 10
q9 q10 q7 //2 slov, konci na 00
<-q10 q10 q10

marros11 · 25. 03. 2010 19:43

ted uz to vidim, dekuji za pomoc s resenim.

Matematické Fórum

#1 23. 03. 2010 19:44

DKA - pro jazyk L a abecedu {0,1}

#2 24. 03. 2010 01:48

Re: DKA - pro jazyk L a abecedu {0,1}

#3 24. 03. 2010 15:47 — Editoval marros11 (24. 03. 2010 19:12)

Re: DKA - pro jazyk L a abecedu {0,1}

#4 25. 03. 2010 18:54

Re: DKA - pro jazyk L a abecedu {0,1}

#5 25. 03. 2010 19:43

Re: DKA - pro jazyk L a abecedu {0,1}

Zápatí