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
#2 11. 03. 2009 18:15
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Jazyky a Automaty
http://forum.matweb.cz/viewtopic.php?id=2638
(jestli je deterministický nebo ne není podstatné).
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#3 26. 03. 2009 17:07
Re: Jazyky a Automaty
Jo prosimte, pises ze neni podstatne jestli je deterministicky nebo ne, ale v kroku 3 mas uvedeno .... Pokud přechod není definován (jinými slovy přechodová funkce není totální), pak skončíme, protože jsme našli slovo, které automat neakceptuje ... ale pokud se nepletu tak ZNKA nemusí mít všechny přechody a nic se neděje není-liž tak?
Offline
#4 26. 03. 2009 17:12
Re: Jazyky a Automaty
Neob mozna jeste lepsi abych to vysvetlil co mam na srdci ...
pises -
Je potřeba ověřit, že
* daný automat má totální přechodovou funkci (tj. že pro každý stav a symbol je určen následující stav)
ale ZNKA nemusi miti totalni prechodove fce a navic muze mit epsilon prechody
Offline
#5 26. 03. 2009 22:03
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Jazyky a Automaty
Tím, že to není podstatné, jsem měl na mysli skutečnost, že oba modely jsou si velmi podobné. Lze proto na začátku nedeterministický stroj převést na deterministický známým algoritmem a pak provést to, co jsem psal dříve.
Když jsem znovu četl, co jsem před rokem napsal, všiml jsem si další nepřesnosti: není nutné, aby přechodová funkce byla totální (definovaná ve všech stavech pro všechny symboly), stačí aby byla definovaná ve všech DOSAŽITELNÝCH stavech pro všechny symboly. To ale odpovídá dříve popsanému algoritmu.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#8 27. 03. 2009 13:25
Re: Jazyky a Automaty
takze tedy diky snad ma posledni otazka.. jednoduche reseni ZNKA prevest na DKA, na nem ukazat ze vsechny stavy jsou prijimaci (vcetne pocatecniho?) a ze prechodove funkce se vsemi symboly vedou do dosazitelnych stavu chapu dobre? jelikoz vetu ... -stačí aby byla definovaná ve všech DOSAŽITELNÝCH stavech pro všechny symboly. To ale odpovídá dříve popsanému algoritmu-.... nevim jestli jsem spravne pochopil, ale myslim ze v DKA musi byt vsechny stavi dosazitelne nebo se mylim? jako ze napr mejme abecedu {a,b,c,d} tak z kazdeho stavu musi vest do nejakeho stavu a,b,c,d neexistuje ze by vedlo jen a,b nebo se mylim?
Offline
#9 27. 03. 2009 13:36
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Jazyky a Automaty
↑ pasl:Jedna věc jsou dosažitelné stavy, druhá věc totální přechodová funkce. Pokud víme, že je funkce totální (tedy jak píšeš, přechod je vždy definován pro všechny znaky nad abecedou), stačí ověřit, že jsou všechny dosažitelné stavy přijímající. Je dost možné, že jste si definovali DKA pouze s totální přechodovou funkcí (jak jsem psal výše, doplnit ji na totální není těžké, takže mezi definicemi by nebyl výrazný rozdíl). Domnívám se ale, že definice nebrání tomu, aby automat obsahoval nedosažitelné stavy.
Třeba automat se stavy 1,2 nad abecedou {a,b} takový, že 1 je počáteční stav a je přijímající, oba přechody z 1 vedou do 1 a oba přechody z 2 také do 1 by měl definici vyhovět.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#10 27. 03. 2009 14:51
Re: Jazyky a Automaty
jasne automat ktery jsi popsal ma nedosazitelny tvar ale take je to automat ktery neni v minimalnim tvaru, ptz nac ze stavu 2 vest prechod a,b do 1 kdyz by k tomuto stacil jen ten 1 pocatecni a zaroven prijimaci stav... ale uvedl jsi dobry priklad tudiz nyni reseni je ZNKA prevest do minimalniho DKA a pote overit zda vsechny stavy vcetne pocatecniho jsou prijimaci a zda z kazdewho stavu vedou totalni prechody ?
Offline