Teoreetilibe informaatika kordamisküsimused
19. Ühe olekuga magasinmäluga automaatide ja Greibachi mõttes
normaliseeritud KV-grammatikate ekvivalentsus.
Iga MMA M jaoks leidub ekvivalentne ühe olekuga MMA M' nii, et T(M) = T(M')
Teeme ühe lõppolekuga MMA M = (,,Q,p,q0,$,F).
F = {*}
Konstrueerime uue MMA M' = (,',Q',p',*,#,{*}).
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:
annaabi.ee 
