Teoreetilibe informaatika kordamisküsimused
Automaadi magasini tähestiku moodustavad sümbolid [sAt] (sümboli A lugemisel
võib masin minna olekust s olekusse t).
Üleminekufunktsioon:
· ([tBx1][x1Cx2][x2Dx3],*) p' (a, [sAx3],*) iga oleku x1x2x3 korral, kui
automaadi M korral (BCD,t) p(a,A,s)
· (,*) p'(a,[sAt],*), kui M korral kehtib (,t) kuulub p(a,A,s)
· p'(,#,*) = {([q0,$,x], *) | x on olek}
Masina tööa algab sammudega (w,#,*)(w,[q0,$q],*)
Igale masina konfiguratsioonile (w,[q1A1q2][q2A2q3]... [qn-1Anqn],*) vastab
korteez
Et näidata genereeritavate keelte samasust, piisab näidata, et M korral kehtib
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.
annaabi.ee 
