Matematické Fórum

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)
* všechny dosažitelné stavy jsou přijímající (ověříme procházením do šířky)
Pokud je obojí splněno, automat akceptuje jakékoliv slovo (tj. akceptuje ). Pokud jedno z toho splněno není, pak automat nevyhoví.
Složitost tohoto algoritmu je MN, kde M je počet stavů automatu a N počet znaků abecedy, což je polynomiální.

Pokud bychmom chtěli pro nějaký jazyk L složitější než zjistit, zda jej A rozpoznává, bylo by potřeba pro L sestavit takový automat, který ho rozpoznává, ten optimalizovat a porovnat s optimalizovanou verzí automatu A. To jde opět v polynomiálním čase (algoritmy na optimalizaci DFA jistě najdeš na internetu, třeba http://is.muni.cz/elportal/estud/fi/js0 … maty_I.pdf ).

Algoritmus by měl pracovat pro a jakýkoliv automat. Pokud chceš  testovat, jak algoritmus funguje, vymysli si automat jakýkoliv. Testování na konkrétním automatu je ale pouze způsob, jak jeho fungování pochopit, ne způsob, jak jeho korektnost dokázat. Domnívám se ale, že u takto jednoduchých algoritmů není potřeba korektnost dokazovat.

Automat pracující nad abecedou sigma pracuje se slovy, které obsahují pouze znaky ze sigma. Víme tedy, že pokud slovo obsahuje znak, který do sigma nepatří, automat ho nepřijme. O tom, která slova automat přijme věta "A (pracuje)/ (přijímá slova) nad Sigma" nic neříká.

Tak to zkusím popsat polopatě, jak ostatně název webu doporučuje :o)

Procházíme do šířky. Máme tedy frontu, do které si ukládáme stavy. Nejdříve si do ní uložíme počáteční stav. Pak postupujeme v krocích, jeden krok se skládá z těchto částí:
1) odebereme stav S z fronty.
2) zapamatujeme si, že stav S už jednou ve frontě byl
3) pro každý symbol abecedy zjistíme, do jakého stavu se tímto symbolem z S přejde.
  - Pokud stav S není přijímající, pak skončíme, protože jsme našli slovo, které automat neakceptuje
  - 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
  - Pokud přechod vede do stavu Q, který ještě nebyl ve frontě, přidáme Q do fronty

Kroky 1), 2) a 3) opakujeme, než nastane situace, že není do fronty co přidat.

Pokud jsme skončili v kroku 3), oznámíme uživateli, že automat jazyk Sigma* neakceptuje. Pokud jsme kroky 1), 2), 3) vždy prošli bez problému, pak oznámíme, že automat jazyk akceptuje.