Pinoautomaatti

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

Kun ää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.

Katso myös

• Chomskyn hierarkia

Lähteet

• Hopcroft, John E., Motwani, Rajeev & Ullman, Jeffrey D.: Introduction to automata theory, languages, and computation. Harlow: Pearson Education Limited, 2014. ISBN 978-1-292-03905-3. (englanniksi)
• Särkilahti, Ari: Pinoautomaateista ja jäsentämisestä. Pro gradu -tutkielma : Oulun yliopisto, matemaattisten tieteiden laitos, matematiikka. Oulu: A. Särkilahti, 2005.