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. Analoogiliselt uvjwxjy ∈ L iga j >= 0 korral. Kui valida vwx alampuu juurest kaugeimate korduvate mitteterminaalide järgi, saab alampuu kõrgus olla maksimaalselt n−1, seega |vwx| <= mn−1 < p. 15 Kontekstist sõltuvad keeled ja Turingi masina keeled. Keel L = {anbncn| n > 0} pole kontekstivaba. T: Lemma järgi jagades uvjwxjy ei kuulu keelde L. Kontekstist sõltuv (KS) keel on selline sõnede hulk, mida genereerib kontekstist sõltuv grammatika.
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 ehitada tuletuspuu. Ei saa eksisteeerida v = x = . Kui saaksime sõna vwx alampuu asendada w alampuuga, ilma, et sõna muutuks saaksime süntaksipuu kõrgusega alla k+1, mis on vastuolus eeldusega. Sellest järeldub, et sisalduvus L1 on alamhulgaks L2, on range. 21. Atribuutgrammatika, programmi semantika leidmine.
annaabi.ee 
