Pinoautomaatti

Wikipedia
Loikkaa: valikkoon, hakuun

Pinoautomaatti on deterministisen äärellisen automaatin (DFA) yleistys, johon liittyy myös pino. Pinoautomaatti on ilmaisuvoimaisempi kuin DFA. Sillä voidaan tunnistaa yhteysriippumaton eli kontekstivapaa kieli.

Kuten äärellinen automaatti mallinnetaan tilojen ja niiden välisten siirtymien joukkona, pinoautomaatti lisää tähän pinon siten, että jokaiseen siirtymään voi liittyä sen siirtymän lisäksi uuden alkion lisääminen pinoon, vanhan alkion lukeminen pinosta pois, molemmat tai pinon pitäminen sellaisenaan. Näistä operaatioista symbolin asettaminen pinoon voidaan suorittaa vapaasti siirtymän yhteydessä, mutta sellainen siirtymä, joka lukisi symbolin pinosta voidaan tehdä, jos ja vain jos pinon päällimmäisenä on jo luettava symboli.

Pinoautomaatin graafinen mallinnus noudattaa myös tyypillisesti äärellisen automaatin mallia; siihen vain lisätään kaariin jokin merkintätapa pinon operaatioille. Tyypillisesti merkintä on sellainen, että kaaren nimen lähettyvillä on merkitty pino-operaatiot muodossa 'lukusymboli/kirjoitussymboli'. Toimintoa, jota ei tehdä, merkitään pinosymbolissakin epsilonilla 'ε' tai lambdalla 'λ', joka tiukan teoreettisen tulkinnan mukaan tarkoittaisi, että pinoon kirjoitetaan tai siitä luetaan ei-mitään.

Automaattiteoria: formaalit kielet ja formaalit kieliopit
Chomskyn
hierarkia
Kielioppi Kieli Tunnistusautomaatti
luokka 0 Rajoittamaton Rekursiivisesti numeroituva Turingin kone
Rajoittamaton Rekursiivinen Totaalinen Turingin kone
luokka 1 Yhteysherkkä Yhteysherkkä Lineaarisesti rajoitettu
luokka 2 Yhteydetön Yhteydetön Pinoautomaatti
luokka 3 Säännöllinen Säännöllinen Äärellinen
Kukin luokka on sen yläpuolisen luokan aito osajoukko.