Rekursiooni ja keerukusteooria eksami konspekt
Teoreem: Iga KV keel on aktsepteeritav mingi magasinmäluga automaadi abil. nt {0n1n | n>0 } vt üleval.
Lõpliku magasinmäluga automaadi poolt aktsepteeritav keel on kontekstivaba. KV keelte hulk ongi see
hulk keeli, mida pinuautomaadid aktsepteerivad.
12 Ühe olekuga pinuautomaatide ja Greibachi mõttes normaliseeritud KV-grammatikate ekvivalentsus.
Teoreem: Iga pinuautomaadi M jaoks leidub ühe olekuga M′, nii et nad aktsepteerivad samu keeli.
T: teeme palindroome (aiassadassaia) aktsepteeriva automaadi, kogu olekute loogika on asendatud
magasini panemise ja sealt võtmise loogikaga.
Teoreem: Ühe olekuga pinuautomaadi M jaoks leidub KV grammatika G, nii et L(M)=L(G).
DEF: KV grammatika on Greibachi normaalkujul, kui tema produktsioonid on kujul A→aA1A2…An või
A→a (muu on tühi sõne) või kujul S → ε, kui keelde L (G) peab kuuluma ka tühi sõne.
Iga KV grammatika on teisendatav Greibachi normaalkujule. T: 1) grammatika peab olema Chomsky nk-l.
annaabi.ee 
