Teoreetilibe informaatika kordamisküsimused
18. Magasinmäluga automaadid
Seadeldis, millel on magasin ja lint ning mis on mõeldud KV keelte
aktsepteertimiseks. Lindilt saab lugeda iga sübolit üks kord sõna vasakult
paremale. Stacki läheb viimase oleku tähis. Töö algul tühja magasini tähis.
Automaadi käitumist määravad käsud kujul:
a lindilt loetav sümbol
A magasinist loetav sümbol
X magasini kirjutatav string
Skeneeritav sõna aktsepteeritakse, kui pärast sõna läbimist on magasin tühi.
Magasinmäluga automaat on struktuur:
M = (,,Q,p,q0,$,F), kus
- sisendtähestik (lint)
magasini tähestik
Q olekute tähestik
p ( U {} x x Q ) üleminekufunktsioon
q0 Q lähteolek
$ - magasini lähtesümbol
F Q lõppolekute hulk
MMA (PDA) konfiguratsioon on kolmik:
(w,,q) * x * x Q
w lindil olev string
magasinis olev string
q hetkeolek
annaabi.ee 
