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). Induktsiooni samm: Eeldame, et võrratus |x| <= mn kehtib kõigi süntaksipuude korral, mille kõrgus n on väiksem kui k. Tuletuspuus kõrgusega k on puu juurel max m alampuud, mille max kõrgus on k-1. Seega kehtib |x| <= mk−1m = mk . T: Iga KV keele jaoks leidub redutseeritud KV grammatika. Olgu sellise grammatika G mitteterminaalide arv n. Valime konstandiks p = mn, kus m on produktsioonide paremate poolte maksimaalne pikkus. Sõne |z| > p tuletuspuu kõrgus peab siis Lemma põhjal olema vähemalt n+1. Seega leidub tuletuspuus tee, millel mingi mitteterminaal A esineb vähemalt 2 korda: Seega uwy ∈ L ja uv2wx2y ∈ L
.,an}
ai on semantiline muutuja hulgast X
Jagame iga sümboli atribuutide hulga kaheks A(Y) = I(Y)US(Y)
I(Y) ühend S(Y) on tühihulk.
Kujutus A defineerib atribuudid igale süntaksipuule.
Süntaksipuu dekoreerimine:
Sõna x atribuutide arvutamine tuletuspuule.
Dekoreerimine algab kõigi atribuutide NIL väärtusel ja kestab, kuni kõigi
atribuutide väärtused olemas.
Atribuutgrammatika korrektne määratlus:
AG = (G,A,R) on korrektselt määratud, kui iga keele sõna x korral on tuletuspuus
kõigi atribuutide väärtused määratud.
Sõna x semantika on väärtus:
(X,k1,..,km) =
annaabi.ee 
