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

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.
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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.