Ne, a1 ei kuulu Ne, siis lülitame P koosseisu kõik reeglid kujul A a0X1a2X2a3 .. Xkak, kus Xi on Bi või (välja arvatud prod A ) o Kui S Ne, lülitada produktsioonide hulka S' S, S' ja luua N' = N U {S'}, vastasel juhul N' = N · G' = {,N',P',S'} Ahelproduktsioonide elimineerimine: IN: KV grammatika G = (,N,P,S) OUT: Ekvivalentne KV grammatika G', milles pole ahelprduktsioone METHOD: · Iga mitteterminaali A jaoks konstrueerime hulga N A = {A | A =>* B}, kus: o N0 = {A}, i = 1 o Ni = Ni-1 U {C | B C on produktsioon, B kuulub Ni} need A-st tuletatavad mitteterminaalid, millest ei saa produktsioonides terminaale o Kui lisandus elemente, teeme veelkorra, kui ei N A = Ni · Konstrueerime hulga P', millesse lisame järgmiselt: o kui produktsioonid B pole ahelproduktsioon, lisame P'-sse A
uvjwxjy erijuht ehk uvjwjxjy= u(vwx)jy. 13 Taandatud KV grammatikad. Iga KV keele jaoks leidub teda genereeriv taandatud KV grammatika: 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
annaabi.ee 
