Baigtinis automatas

Baigtinis automatas – matematinė abstrakcija, modeliuojanti sistemos būsenų kaitą, priklausomai nuo ankstesnės būsenos ir įėjimo signalų, kai būsenų ir galimų įėjimo signalų skaičius yra baigtinis (nuo to ir pavadinimas).

Nesudėtingo Milio automato būsenų kaitos diagrama

Baigtinio automato, generuojančio kalbą, aprašomą reguliariąja išraiška a(bc)*d, būsenų kaitos diagrama

Esama įvairių baigtinių automatų atmainų. Pavyzdžiui, kompiuterių projektavimui naudojami baigtiniai automatai turi išėjimus. Pagal išėjimų formavimo mechanizmą skiriami Muro ir Milio automatai. Muro automatų išėjimo reikšmė priklauso tik nuo buvusios jo būsenos, o Milio automato – ir nuo įėjimo signalo reikšmės.

Formalių kalbų analizei ir generavimui skirti baigtiniai automatai neturi išėjimų, bet turi galines būsenas. Jei po baigtinės įėjimų signalų sekos (vadinamos žodžiu) automatas patenka į vieną iš galinių būsenų, sakoma, kad automatas priima šį žodį ir šis žodis priklauso automato generuojamai kalbai.

Baigtiniai automatai dažnai vaizduojami grafais ar jiems giminingomis diagramomis. Baigtinio automato būsenos vaizduojamos grafo viršūnėmis, o perėjimai tarp jų – lankais.

Baigtiniai automatai skirstomi į deterministinius ir nedeterministinius. Deterministiniai automatai kiekvienai esamos būsenos bei įėjimo signalo kombinacijai turi tik vieną įmanomą atsakomąjį būsenos kitimą. Be įėjimo signalų, „sava inciatyva“ mašina būsenos nekeičia. Nedeterministiniai automatai tai pačiai būsenai ir signalui gali turėti daugiau galimų kitimų ir kai kada keisti būseną savaime (ϵ kitimai). „Nedeterministinis“ nereiškia automato, kurio elgesys tiesiog neprognozuojamas. Visada galima aprašyti sudėtingesnį bet deterministinį automatą, kurio atsakas į tą patį įėjimo signalą toks pats, kaip nagrinėjamo nedeterministinio.