Teoreetilibe informaatika kordamisküsimused
· 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
teise A alampuude vahele, x teise a teise A parema ja esimese A parema vahele.
y esimese A parema ja stardisümboli parema vahele.
vwx sõnale vastava alampuu kõrgus on väiksem, kui k+1. Seega võime valida q
= mk+1 > |vwx|.
Kui eemaldame sõna vwx alampuu ja asendame selle w alampuuga, saame
v0wx0 (ehk uwy) sõna.
Asendades aga esialgse w alampuu (korduvalt) terve sõna vwx alampuuga,
saame sõna uvtwxty tuletuse, mis kuulub ka keelde, kuna sellele on võimalick
annaabi.ee 
