Oletame, et väide kehtib, kuni kõrguseni k-1. Näitame, et sel korral kehtib sõna w süntaksipuu jaoks kõrgusel k. Sellise puu juurel max m vahetut alluvat, mille alluvate alampuude max kõrgus k- 1. Teiste puude kroonide pikkus on eelduse kohaselt m k-1. Kogu puu jaoks aga |Kr(T)| <= m * mk-1 = mk KV keelte tarvilikkuse tingimus: Kui L on KV keel, leiduvad ainult keelest L sõltuvad konstandid p ja q nii, et L sõna z korral kui |z|>p, siis leidub jaotus z = uvwxy, kusjuures: · |vwx| < q · v ja x pole korraga tühjad sõnad · iga i korral kuulub keelde ka uviwxiy Tõestus: G = (,N,P,S), L(G), max produktsioooni pikkus m. k = |N|. Valime p = mk, |z|>p. Tuletuspuu kõrgus peab olema vähemalt k+1 seega peab mingi mitteterminaal esinema selle puu pikimal teel vähemalt 2 korda. Valime kaks viimast mitmekordse mitteterminaali esinemist ja jaotame sõna puuks, mille u osa jääb vasakpoolseima ja A esimese vasakpoolseima alampuu
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; 3) ei sisalda saavutamatuid sümboleid (mis nkn ei teki ühegi produktsiooni käigus kunagi); 4) tsüklivaba ehk ühegi mitteterminaali ei saa temast endast tuletada. 1. ja 4
annaabi.ee 
