Pinoautomaatti
Wikipedia
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. | |||
