Teoreetilibe informaatika kordamisküsimused
seos:
(w,$,q0)*(w',,q) parajasti siis, kui M' korral kehtib
*
(erijuhul lõppkonfiks (,,r) ja <,,r>)
Tõestus:
k=0
(w,$,q0)0 (w,$,q0)
M' korral (w,#,*)0 (w,[q0$q],*) ehk 0
Induktsioonibaas on olemas.
Eeldame, et tehtud on i takti
Näitame, et kehtib i+1 takti korral samuti.
(w,$,q0)i (aw',A,qi) (w,BCD,qi+1)
Mis on võimalik juhul:
(BCD,qi+1) p(a,A,qi)
M' konstruktsiooni põhjal:
([qi+1Bp1][p2Cp3][p3Dp4],*) p' (a,[qiAp4],*), kus pi on olekud.
Induktsiooni eelduse kohaselt saame nüüd:
*
Iga magasinmäluga automaadi jaoks leidub kontekstivaba grammatika, nii et
T(M) = L(G)
Eeldame, et MMA on ühe olekuga (kuna igale ühe olekuga sai vastavusse seada
ekvivalentse mitme olekuga MMA).
M = (,,{*},p,*,Z,{*})
Olgu grammatika:
G = (,N,P,S) produktsioonid järgmiselt:
A B1..Bk saagu produktsiooniks, kui B1..Bk p(a,A), k>=0
A B1.
annaabi.ee 
