2022 AFJ Cvičenie č. 2 - Konečné automaty

Zhrnutie prednášky

Cvičenie nadväzuje na prednášku o konečných automatoch a ukazuje, ako určiť jazyk, ktorý daný automat akceptuje. Na príklade automatu s tromi stavmi q0, q1, q2 a vstupnou abecedou {0,1} sa krok za krokom simuluje výpočet pre reťazce 0, 1, 001 a 000. O akceptovaní rozhoduje stav, v ktorom automat skončí po prečítaní celého vstupu, a to podľa toho, či patrí do množiny akceptačných stavov F. Z prechodovej funkcie vyplýva, že q2 je pasca, z ktorej sa nedá vyjsť, takže automat akceptuje len neprázdne reťazce zložené zo samých núl, teda jazyk 0⁺, nie 0*. Na záver sa zavádza prechodový diagram, teda orientovaný graf, ako názornejší zápis automatu.

• - Jazyk automatu tvoria všetky reťazce, ktoré ho po prečítaní celého vstupu dostanú do akceptačného stavu.
• - Výpočet sa simuluje symbol po symbole pomocou prechodovej tabuľky a konfigurácií (stav, zvyšok vstupu).
• - Akceptovanie závisí len od prechodovej funkcie a od množiny akceptačných stavov F.
• - Stav q2 je pasca: po vstupe do neho automat zostáva v ňom pri 0 aj 1, takže reťazec s jednotkou sa neakceptuje.
• - Jazyk príkladového automatu je 0⁺; prázdny reťazec sa neakceptuje, lebo q0 nie je akceptačný.
• - Prechodový diagram je orientovaný graf: vrcholy sú stavy, počiatočný stav má vstupnú šípku a akceptačné stavy sú obkrúžené dvojitou kružnicou.

Zhrnutie pripravené s pomocou AI z prepisu videa.