3. Konečné automaty jako převodníky, Mealyho a Mooreův automat

Question 1

Konečné automaty

Answer 1

matematické modely, které se používají k rozpoznání jazyků

přijímají a generují řetězce symbolů

automat může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu

Question 2

Konečné automaty jako převodníky

Answer 2

Převodníky se liší od akceptorů tím, že produkují výstup

Při použití konečného automatu jako převodníku se vstupní řetězec předává do automatu, který následně prochází stavy podle symbolů vstupního řetězce

Pokud automatu dokončí procházení vstupního řetězce, výstupem je nějaký zpracovaný výstupní řetězec, který byl vygenerován automatem

Převodník v každém kroku svého běhu:
1, Přečte jeden symbol ze vstupu
2, Posune hlavu o jeden symbol vpravo
3, Vloží jeden symbol na výstup

Převodníky pracují DETERMINISTICKY

Question 3

Mealyho automat

Answer 3

používá se k transformaci vstupních řetězců na výstupní řetězce

Mealyho automat generuje výstup na základě vstupu a aktuálního stavu

Mealyho automat definuje výstupní symbol pro každý PŘECHOD

Tyto automaty jsou často používány k návrhu řadičů pro digitální systémy

Ke každému Mooreovu automatu lze sestrojit ekvivalentní Mealyho automat a obráceně

Běh Mealyho automatu:
1, Přechodová funkce definuje přechod (qi, a) → qj. Je-li automat ve stavu qi a jestliže čte znak a, potom přejde do stavu qj
2, Přechod je deterministický a je vždy definován
3, Generuje výstupní symbol na základě vstupu a aktuálního stavu podle výstupní funkce

Question 4

Mooreův automat

Answer 4

používá se k transformaci vstupních řetězců na výstupní řetězce

Mooreův automat generuje výstup pouze na základě aktuálního stavu

Mooreův automat definuje výstupní symbol pro každý STAV

Mooreovy automaty se používají k modelování nebo řízení různých systémů (např.: robotické systémy)

Ke každému Mooreovu automatu lze sestrojit ekvivalentní Mealyho automat a obráceně

Běh Mooreova automatu:
1, Počáteční stav automatu je q0 a v registru je slovo w
2, Předpokládejme, že v n-tém kroku stav automatu je qi, čtecí hlava je nad políčkem se znakem a
3, Potom pokud platí δ (qi, a) = qj a θ(qj) = b, automat posune hlavu o jedno políčko vpravo, přejde do stavu qj a vygeneruje výstup b