Teoreetilibe informaatika kordamisküsimused
produktisiooni paremas pooles.
Tühja parema poolega reeglite elimineerimine:
IN: KV grammatika G = (,N,P,S)
OUT: Ekvivalentne KV grammatika G', milles pole -reegleid
METHOD:
· Keele tühjuse algoritmiga koostame hulga Ne.= {A | A =>* e}
· Konstrueerime hulga P:
o kui A a0B1a1B2a3 .. 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
annaabi.ee 
