Teoreetilibe informaatika kordamisküsimused
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
vahele, v esimese A vasakpoolse ja teise A vasakppolse alampuu vahele, w
annaabi.ee 
