To tylko jedna z 12 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
4.6. Gramatyki regularne
G = jest gramatyką prawostronnie liniową, jeśli jej produkcje mają postać:
(i )U → xV
*
x∈T U,V∈N
(ii )U → x
G = jest gramatyką prawostronnie regularną, jeśli jej produkcje mają postać :
(i )U → aV
a∈T U,V∈N
(ii )U → a
oraz (iii) jeśli (Z→ε)∈P to Z nie występuje w prawych stronach żadnej produkcji.
(Często w definicji gramatyki regularnej pomija się warunek (iii) dotyczący niewystępowania
Z w prawych stronach produkcji – dopuszcza się za to produkcję U→ε ; U∈N)
Analogicznie określa się :
-gramatyki lewostronnie liniowe
U → Vx
*
x ∈T U,V∈N
U→x
-gramatyki lewostronnie regularne
U → Va
a∈T U,V∈N
U →a
Szkic algorytmu przekształcania gramatyki prawostronnie liniowej w prawostronnie
regularną.
We: G = ∈ GPLN
Wy: G’ = ∈ GPRG
L(G) = L(G’)
Metoda:
P’ := P;
N’ := N;
for (A → α) ∈ P do
begin
if α = xB and x = x1...xn∈ T* and |x| ≥ 2 then
begin
C := { A → x1C1 ; C1 → x2C2 ; ... ; Cn-1 → xnB };
P’ := P’ \ { A → xB } ∪ C ;
N’ := N’ ∪ { C1,...,Cn-1 } ;
end;
if α = x and x = x1...xn ∈ T* and |x| ≥ 2 then
begin
C := { A → x1C1 ; C1 → x2C2 ; ... ; Cn-1 → xnB };
P’ := P’ \ { A → x } ∪ C ;
N’ := N’ ∪ { C1,...,Cn-1 } ;
end;
end;
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 :
A → aA1
A → abB
A1 → bB
A → aA1
A1 → bB
A → aA1
A1 → bB
A → ba
A → bA2
A2 → a
A → bA2
A2 → a
A → bA2
A2 → a
B→ b
B→ A
B→ ε
B→ b
B→ A
B→ ε
B→ b
B→ b
B→ A → {B→ aA1
A1→ b
{B→ bA2
Usunięcie
Gramatyka
Prawostronnie
liniowa
Usunięcie
ε - prod.
prod.. łańcuchowych
Gramatyka prawostronnie
regularna
Przekształcenie gramatyki lewostronnie regularnej w prawostronnie regularną.
We: G = ∈ GLRG
G – nie zawiera symbolu początkowego Z w prawych stronach produkcji
Wy: G’ = ∈ GPRG
Taka, że L(G’) = L(G)
Metoda:
P’ := ∅;
N’ := N ∪ {Z’} \ {Z}
for (A→ a) ∈ P : a∈T do
if A=Z then P’ := P’ ∪ {Z’→ a}
else P’ := P’ ∪ {Z’→ aA};
for (A→ Ba) ∈ P : B∈N , a∈T do
if A=Z then P’ := P’ ∪ {B→ a}
else P’ := P’ ∪ {B→ aA};
Przykład:
G =
S→a
S → Ab
A→a
A → Ab
G’ =
S’ → a
A→b
S’ → aA
A → bA
Usuwanie reguł końcowych ( kosztem wprowadzenia ε - produkcji )
Produkcje końcowe : U → a : U∈N , a∈T
We : G = ∈ GPRG
Wy : G’ = - bez produkcji końcowych , taka ,że L(G’) = L(G)
Metoda:
N’ := N;
P’ := P;
for (A→ x) ∈P do
if x∈T then
begin
N’ := N’∪ {Ax};
P’ := P’ ∪ { A → xAx , Ax→ ε}
– { A → x};
end;
Przykład :
G =
S → bS
S → bS
S → aA
S → aA
S → aB
S → aB
B → bC
B → bC
C → aA
C → aA
A → bR
A → bR
Symbol końcowy (nie mylić z symbolem terminalnym)
Q → aB
Q → aB
A→b
A → bD , D → ε
Wykres gramatyki (bez produkcji końcowych w postaci grafu zorientowanego )
A
Z
symbol początkowy
gramatyki
a
a
B
B
A → aB A,B
... zobacz całą notatkę
Komentarze użytkowników (0)