"aa1a2a3" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

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. 
 2) mitteterminaalid nimetatakse ümber A1-ks, A2-ks jne. 3) produktsioonid asendatakse kujule aA1A2A3… Regulaarsete keelte hulk on KV keelte pärisosahulk. Vaatame kasvõi pumpamise lemmasid: uvjw on lihtsalt uvjwxjy erijuht ehk uvjwjxjy= u(vwx)jy. 13 Taandatud KV grammatikad. Iga KV keele jaoks leidub teda genereeriv taandatud KV grammatika: 1) ε-vaba (puuduvad tühja parema poolega produktsioonid, v.a S → ε, kui ε kuulub sellesse keelde) 2) ei sisalda kasutuid sümboleid ehk mitteterminale, millest ei saa tuletada terminaalseid sõnesid;