4) tsüklivaba ehk ühegi mitteterminaali ei saa temast endast tuletada. 1. ja 4. tingimuse täitmiseks piisav, kui eemaldada ε-d ja ahelproduktsioonid. Eemaldada tuleb ka sümbolid, milleni nkn kunagi ei jõuta. Ja tuleb vaadata, et S * wXy * wxy (lõpuks aint terminaalid). 14 KV-keelte tarvilikkuse tingimus. Teoreem: Kui L on KV keel, siis leidub konstant p, nii et iga sõne z ∈ L, |z| > p korral saab selle jaotada z = uvwxy, kus |vx| > 0 (olemas on nii v kui x), |vwx| <= p (ees ja taga võib, aga ei pea veel mingeid tähti olema) ja uvjwxjy ∈ L iga j = 0,1,2,... puhul. Lemma: Olgu sõne x tuletuspuu kõrgus KV grammatikas k, siis |x| <= mk, kus m on selle grammatika produktsioonide paremate poolte maksimaalne pikkus. Induktsiooni baas: k=1 korral on sõne x tuletatud produktsiooni S → x abil. (kohe otse, puu kõrgus on 1) Seega |x| <= m = m1 = mk (kuna k=1 ja max m on x pikkus).
Induktsioonisamm: 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
annaabi.ee 
