Teoreetilibe informaatika kordamisküsimused
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
Töötaktiks on binaarne relatsioon konfiguratsioonide hulgal:
(aw,Za,q) (w,a,q'), kui (,q') kuulub p(a,Z,q)
OR
(w,Za,q) (w,a,q'), kui (,q') kuulub p(,Z,q)
MMA poolt aktsepteeritav keel on hulk:
T(M) = {w | (w,$,q0)*(,,r) , kus r on üks lõppolekutest}
Iga KV keele jaoks leidub MMA, nii et L = T(M):
G = (,N,P,S)
Tõestuseks konstrueerime automaadi M nii:
M = (,,Q,p,q0,$,F)
= U N U {$}
Q = {q0,q1,q2}
Üleminekufunktsioon:
annaabi.ee 
