Témata nápovědy
Konečný automat
Existuje několik typů konečných automatů, nedeterministický, deterministický, úplný, dobře specifikovný a minimální. Každý automat je dán pěticí M=(Q,E,R,s,F), kde Q je konečná množina všech stavů, E je abeceda vstupních symbolů, R je konečná množina pravidel(přechodů), s je jeden z prvků množiny Q, jedná se o počáteční stav, F je konečná množina stavů, které jsou koncové.Říkáme, že řetězec byl automatem přijat, pokud jsme se z počátečního stavu použitím libovolných pravidel v libovolném pořadí dostali do kteréhokoliv koncového stavu. Každý konečný automat jde reprezentovat několika způsoby: například tabulkou, matematicky, graficky. Tento program využívá grafického zobrazení.
Tento program dokáže zkontrolovat, zda zadaný automat je deterministickým. Toto lze provést přes menu - nejprve stiskněte "automat", potom "Zkontrolovat, jestli je DFA".Proběhne kontrola a otevře se okno s odpovědí, zda daný automat je, či není deterministický.
V programu je také k dispozici funkce, která převede automat na deterministický. Tato funkce lze vyvolat opět přes menu (Automat, Zkonvertovat na DFA) a nebo stiskem tlačítka "DFA" na panelu nástrojů. Objeví se okno s upozorněním, že změny budou trvalé a nelze je vrátit. Po potvrzení je automat převeden na deterministický.
Nedeterministický automat
Tento automat je specifický tím, že může obsahovat
- epsilon přechody
- stavy, ze kterých se lze pomocí jednoho symbolu dostat do více stavů
- nedostupné a neukončující stavy
Příklad nedeterministického automatu:
Deterministický automat
Tento automat je specifický tím, že narozdíl od předcházejícího
- nesmí obsahovat epsilon přechody
- se lze z jednoho stavu pomocí jednoho symbolu dostat maximálně do jednoho stavu
- shodně s předcházejícím může obsahovat nedostupné a neukončující stavy
Příklad deterministického automatu: (Automat byl vytvořen funkcí na převedení deterministického automatu na deterministický z výše uvedeného nedeterministického automatu)
Úplný deterministický automat
Tento automat je specifický tím, že narozdíl od předcházejícího
- jak již název napovídá, jedná se o deterministický automat
- je zde přidán stav false, což je stav, do kterého se dostanu, pokud z daného stavu pro daný symbol neexistuje jiný přechod => z každého stavu se přijetím jakéhokoliv písmenka musím někam dostat, v případě, že se dostanu do stavu false, který není koncový, tak řetězec automatem přijat nebyl
Dobře specifikovaný automat
Jedná se o úplný deterministický automat, navíc
- nemá nedostupný stav
- nemá více než jeden neukončující stav
Minimální automat
Jedná se o dobře specifikovaný automat, navíc platí
- je právě jeden pro daný jazyk