Teoreetilibe informaatika kordamisküsimused
. Bkak on produktsioon (k>= 0), Bi kuulub
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
annaabi.ee 
