95993

Usunąć £ - produkcję (w razie potrzeby);

Usunąć reguły łańcuchowe;

Usunąć symbol początkowy z prawych stron produkcji (w razie potrzeby); /* algorytm usuwania symbolu początkowego będzie podany później */

Przykład:

> abB

f A -* a A,	f A —»aA,	| A -» aA,
[A, ->I>B	1 A, ->/;«	[a, ->/>/(
| A -» bA,	[A —> bA,	f A -» bA,
1 a2	[A, —> a	[Aj -><I
B-r b	B-» b	B-» b

> ba

Gramatyka prawostronnie regularna

Przekształcenie gramatyki lewostronnie regularnej w prawostronnie regularna We: G = < N,T,P,Z > e Glro

G - nie zawiera symbolu początkowego Z w prawych stronach produkcji

Wy: G’ = < N',T,P',Z’> £ G,._RO Taka, że L(G’) = L(G)

Metoda:

P' := 0;

N’ :=Nu{Z’H|Z) for (A-» a) e P : aeT do

if A=Z tlien P’ := P’ u {Z’-» a) else P’ := P’ u {Z’-> aA}; for (A-» Ba) e P : BeN , ae T do if A=Z tlren P’ := P’ u {B-> a) else P’ :=P’u {B-»aA};