Rekursiooni ja keerukusteooria eksami konspekt
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.
annaabi.ee 
