95997

No :=    /*<)>- zbiór pusty */

i :=0; repeat

i :=i+ 1;

Ni := Nj., u { A g N | (A->a) g P a ot g (N„iuT)' } until N. = N,.i'.

Gi := < N n Ni, T, Pi, Z> gdzie

Pi := {(u-»v) e P | u,v e (NiuT)’};

zastosować do Gi algorybn usuwania symboli nieosiągalnych uzyskując w wyniku tego gramatykę G’ = <N\ T’, P’, Z>

Przykład:

G = <{S, A, B}, {a, b), {S-»a ; S-»A ; A-»AB ; B->b},S>

G, = <{S, B), {a, b}, {S-»a ; B->b}, S>

G’ = <{S}, {a}, {S-»a>, S>

Algorytm usuwania e-produkcii w_e:    G = <N, T, P, Z>g Gka

w_y:    G’ = <N’,T, P’, Z’> g Ghk taka, że:

(i)    UG) = L(G’)

(ii)    G’ jest gramatyką bez e-produkcji Metoda:

N₀ := ó. /*<)>- zbiór pusty */

i := 0; repeat

i:=i+ 1;

Ni := Nu u { A g N | (A-»x) g P a xg N,.,' ); until N. = N.-i:

N« := Ni;    /* N_e = {A | AgN aA =>⁺g e) */

P^- := P;

for(A-»x)G Pdo begin

przedstawiamy „x” w postaci OoBiOtiBjOtj... BkOtk, k > 0, gdzie B, g N, (1 Si < k), a, e ((NuT)-N_e)’ (0< i <k),

P’ := P’ u {(A -> aoX,aiX₂a2 ... X_kotk): (Xi= B, v Xi = e)>;

if (A->e) g P’ tlien P’ := P’ - {(A->e)};

end:

if Z g N_c then begin

N’:=Nu {Z’};