To tylko jedna z 7 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
3.4. Przekształcenia gramatyk bezkontekstowych
Definicje
Niech będzie dana gramatyka bezkontekstowa G = ∈ GBK
Symbol X ∈ (N∪T) nazywamy nieużytecznym w G∈GBK jeśli nie można w tej gramatyce
przeprowadzić wyprowadzenia: Z ⇒*G wXy ⇒*G wxy przy czym w,x,y ∈ T* (czyli z X nie
można wyprowadzić żadnego słowa w symbolach terminalnych).
Symbol X ∈ (N∪T) nazywamy nieosiągalnym w G∈GBK, jeśli X nie pojawia się w żadnej
formie zdaniowej tej gramatyki (czyli nie można go wyprowadzić z Z).
Gramatyka G∈GBK jest gramatyką bez ε-produkcji, gdy:
(i) P nie zawiera produkcji postaci A→ε, A∈N, A≠Z
(ii) jeśli (Z→ε) ∈ P to symbol Z nie występuje w prawych stronach pozostałych
produkcji
Algorytm usuwania symboli nieosiągalnych
wejście:
G = ∈ GBK
wyjście:
G’ = ∈ GBK taka, że
(i) L(G’) = L(G)
(ii) ( ∀ X∈(N’∪T’) ) ( ∃ α,β∈(N’∪T’)* ) ( Z ⇒*G’ αXβ )
Metoda:
V0 := {Z};
i := 0;
repeat
i := i + 1;
Vi := Vi-1 ∪ {X ∈ (N∪T) | (A→αXβ) ∈ P ∧ A ∈ Vi-1 ∧ α,β ∈ (N∪T)* };
/* Vi zawiera te symbole terminalne i nieterminalne które:
until Vi = Vi-1 ;
- występują w produkcjach z P
- dają się wyprowadzić z Z */
N’ := Vi ∩ N;
T’ := Vi ∩ T;
P’ := {(u→v) ∈ P | u,v ∈ V*i }
/* zawiera te produkcje z P, które zbudowane są
z symboli z Vi */
G’ :=
Algorytm usuwania symboli nieużytecznych
wejście:
G = ∈ GBK
wyjście:
G’ = ∈ GBK taka, że:
(i) L(G’) = L(G)
(ii) (N’∪T’) nie zawiera symboli nieużytecznych
Metoda:
N0 := φ;
/* φ - zbiór pusty */
i := 0;
repeat
i := i + 1;
Ni := Ni-1 ∪ { A ∈ N | (A→α) ∈ P ∧ α ∈ (Ni-1∪T)* }
until Ni = Ni-1;
G1 := gdzie
P1 := {(u→v) ∈ P | u,v ∈ (Ni∪T)* };
zastosować do G1 algorytm usuwania symboli nieosiągalnych uzyskując w wyniku tego
gramatykę G’ =
Przykład:
G =
G1 =
G’ =
Algorytm usuwania ε-produkcji
we:
G = ∈ GBK
G’ = ∈ GBK taka, że:
(i) L(G) = L(G’)
(ii) G’ jest gramatyką bez ε-produkcji
Metoda:
N0 := φ; /* φ - zbiór pusty */
i := 0;
repeat
i:= i + 1;
Ni := Ni-1 ∪ { A ∈ N | (A→x) ∈ P ∧ x ∈ Ni-1* };
until Ni = Ni-1;
Ne := Ni ;
/* Ne = {A | A ∈ N ∧ A ⇒+G ε} */
P’ := P ;
for (A→x) ∈ P do
begin
przedstawiamy „x” w postaci α0B1α1B2α2 ... Bkαk, k ≥ 0,
gdzie Bi ∈ Ne (1 ≤ i ≤ k), αi ∈ ((N∪T) – Ne)* (0 ≤ i ≤ k);
P’ := P’ ∪ {(A → α0X1α1X2α2 ... Xkαk) : (Xi= Bi ∨ Xi = ε)};
if (A→ε) ∈ P’ then P’ := P’ – {(A→ε)};
end;
if Z ∈ Ne then
begin
N’ := N ∪ {Z’};
wy:
P’ := P’ ∪ {(Z’ → Z), (Z’ → ε)};
Z’ := Z’;
end
else
begin
N’ := N;
Z’ := Z;
end;
Przykład:
S → aSbS
S → bSaS
S→ε
Po usunięciu S → ε otrzymujemy
S’ → S
S’ → ε
S → aSbS , S → aSb , S → abS , S → ab
S → bSaS , S → bSa , S → baS , S → ba
Usuwanie produkcji łańcuchowych i cykli
Produkcje łańcuchowe, to produkcje postaci: A → B ; A, B ∈ N
Gramatyka G zawiera cykle, wówczas gdy istnieją w gramatyce wyprowadzenia postaci
A ⇒+G A ; A ∈ N
Algorytm usuwania produkcji
... zobacz całą notatkę
Komentarze użytkowników (0)