Baigtinis automatas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
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

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).

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.



Vikiteka