Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
- Hlavní strana
- » Ostatní zajímavé dotazy a úlohy, dotazy pro praxi
- » DKA - pro jazyk L a abecedu {0,1} (TOTO TÉMA JE VYŘEŠENÉ)
#1 23. 03. 2010 19:44
DKA - pro jazyk L a abecedu {0,1}
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.
Offline
- (téma jako vyřešené označil(a) Kondr)
#2 24. 03. 2010 01:48
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: DKA - pro jazyk L a abecedu {0,1}
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.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#3 24. 03. 2010 15:47 — Editoval marros11 (24. 03. 2010 19:12)
Re: DKA - pro jazyk L a abecedu {0,1}
↑ 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
Offline
#4 25. 03. 2010 18:54
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: DKA - pro jazyk L a abecedu {0,1}
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
BRKOS - matematický korespondenční seminář pro střední školy
Offline
Stránky: 1
- Hlavní strana
- » Ostatní zajímavé dotazy a úlohy, dotazy pro praxi
- » DKA - pro jazyk L a abecedu {0,1} (TOTO TÉMA JE VYŘEŠENÉ)