"pinuautomaatide" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

Automaat aktsepteerib sõne, kui ta alustab lähteolekust ja tühja magasiniga ning jõuab aktsept. olekusse. a,b → c (sisend, magasinist loetu = magasini pandu) ε - sisendist v magasinist ei loeta v ei kirjutata sinna 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