Rekursiooni ja keerukusteooria eksami konspekt
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.
KS keeltel on erinevad produktsioonid cB →… ja bB →… sest muutumine sõltub, kas B ees on b või c.
DEF: KS grammatika on nelik G = (N,Σ,P,S), kus N on mitteterminaalide tähestik; Σ on terminaalide
annaabi.ee 
