Rekursiooni ja keerukusteooria eksami konspekt
1) ε-vaba (puuduvad tühja parema poolega produktsioonid, v.a S → ε, kui ε kuulub sellesse keelde)
2) ei sisalda kasutuid sümboleid ehk mitteterminale, millest ei saa tuletada terminaalseid sõnesid;
3) ei sisalda saavutamatuid sümboleid (mis nkn ei teki ühegi produktsiooni käigus kunagi);
4) tsüklivaba ehk ühegi mitteterminaali ei saa temast endast tuletada.
1. ja 4. tingimuse täitmiseks piisav, kui eemaldada ε-d ja ahelproduktsioonid. Eemaldada tuleb ka
sümbolid, milleni nkn kunagi ei jõuta. Ja tuleb vaadata, et S * wXy * wxy (lõpuks aint terminaalid).
14 KV-keelte tarvilikkuse tingimus.
Teoreem: Kui L on KV keel, siis leidub konstant p, nii et iga sõne z ∈ L, |z| > p korral saab selle jaotada
z = uvwxy, kus |vx| > 0 (olemas on nii v kui x), |vwx| <= p (ees ja taga võib, aga ei pea veel mingeid tähti
olema) ja uvjwxjy ∈ L iga j = 0,1,2,... puhul.
annaabi.ee 
