G = < N,T,P,Z > jest gramatyką prawostronnie liniową, jeśli jej produkcje mają postać: i
( U
) → xV x∈T* U,V∈N
ii
( U
) → x
G = < N,T,P,Z > 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 → Vaa∈T U,V∈N
U → a
Szkic algorytmu przekształcania gramatyki prawostronnie liniowej w prawostronnie
regularną.
We: G = < N,T,P,Z > ∈ GPLN
Wy: G’ = < N,T,P,Z > ∈ 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 → aA
A → aA
A → aA
A → abB
1
1
1
A
A
A 1 →
1 →
1 → bB
bB
bB
A → bA
A → bA
A → bA
A → ba
2
2
2
A
A
A 2 →
2 →
2 → a
a
a
B→ b B→ b B→ b B→ b
B→ A B→ A B→ A → {B→ aA1
B→ ε B→ ε A1→ b {B→ bA2
Usunięcie Usunięcie
Gramatyka ε - prod. prod.. łańcucho-
Prawostronnie wych
liniowa
Gramatyka prawostronnie
regularna
Przekształcenie gramatyki lewostronnie regularnej w prawostronnie regularną.
We: G = < N,T,P,Z > ∈ GLRG
G – nie zawiera symbolu początkowego Z w prawych stronach produkcji
Wy: G’ = < N’,T,P’,Z’> ∈ 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};
G = < {S,A},{a,b},P,S > G’ = <{S’,A},{a,b},P’,S’ >
S → a S’ → a
S → Ab A → b
A → a S’ → aA
A → Ab A → bA
Usuwanie reguł końcowych ( kosztem wprowadzenia ε - produkcji )
Produkcje końcowe : U → a : U∈N , a∈T
We : G = < N,T,P,Z > ∈ GPRG
Wy : G’ = < N’,T,P’,Z > - 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,A,B,C,R,Q},{a,b},P,S >
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 A → aB A,B ∈N a∈T A≠Z (B→ ε) ∉P
A
B
a Z
Z
B
→ aB a∈T , B∈N (B→ε) ∉P
symbol początkowy
gramatyki
A
a A
B
→ aB a∈T A,B∈ N
symbol końcowy
Przykład : b
R
S → bS
S → aA b
S → aB a b
S
A
D
B → bC
C → aA a a
A → bR b
Q → aB
B
C
A → bD
D → ε a
R
Q
b
b
Usuwanie symb. nieosiągalnych . a b S
A
D
Można usunąć każdą produkcję
U → aV, taką,że U≠Z oraz symbol a a U nie występujący po prawej stronie b B
C
Żadnej produkcji.
a
Q
nieosiągalny
Usuwanie symb. nieużytecznych.
R
Można usunąć wszystkie produkcje nieużyteczny U → aV , gdzie V nie jest symbolem b b Końcowym oraz V nie występuje a b Po lewej stronie żadnej produkcji
S
A
D
, z wyjątkiem być może produkcji
typu V → aV a a b
B
C
a b
S
A
D
a a
b
B
C
Powyższe stwierdzenia nie są precyzyjne. Dokładne algorytmy podano dla gramatyk
bezkontekstowych. ( GRG ⊂ GBK )
Przypomnienie :
Ścieżka – ciąg wierzchołków grafu zgodny z istniejącymi krawędziami i ich zorientowaniem Def. Ścieżka końcowa ! Ścieżka
K0 K1 ... Kn taka, że
K0 = Z
Kn ∈ zbiór symboli końcowych
Ścieżka wyznaczona przez słowo x=x1 x2 ...xn ! ścieżka końcowa K0 K1 ...Kn taka, że K0 → x1 K1
K1 → x2 K2
...
Kn-1 → xn Kn
Kn → ε
x ∈ L(G) ! ∃ ścieżka wyznaczona przez słowo x
Tw. Język generowany prze gramatykę prawostronnie regularną (bez produkcji końcowych) jest językiem regularnym (tzn. określonym przez wyrażenie regularne). [Dowód prze indukcję względem ilości krawędzi w grafie].
Z gramatyki prawostronnie regularnej usuwamy jedną produkcję typu Z → aA ( Z – symb.
początkowy).
Rozważamy cztery gramatyki :
G
1 G2
a
a
Z
A
Z
A
G3 G
4
a
Z
a
A
Z
A
W G2 jedynym wierzchołkiem początkowym i końcowym jest Z.
W G3 wierchołkiem początkowym jest A i jedynym końcowym jest Z.
L(G) = L(G1) ∪ L(G2) [ aL(G3)]*aL(G4)
Każda ścieżka końcowa w G jest albo końcowa w G1 albo może być przedstawiona w postaci: x a y1 a y2 … a ym a z
ścieżka końcowa ścieżki koncowe ścieżka końcowa
w G2 w G3 w G4
Przykład :
Zbudować wyrażenie regularne
Opisujące język generowany przez
G b gramatykę daną grafem.
a b
S
A
D
a a
b
B
C
G b
1
b L(G1) = {bnabab | n ≥ 0} =
= [
S
A
D
b*abab]
a
a
b
B
C
G b
2
B b
S
A
D
≡ L(G2) = {bn | n ≥ 0} =
= [
S
b*]
a
b
B
C
G b
3
b
S
A
D
≡ L(G
A
3) = ∅ = [ϕ]
a a
b
B
C
G b
4
L(G4) = {b} =
B
S
A
= [
D
b]
≡ b
A
D
a a
b
B
C
L(G) = L(G1) ∪ L(G2) [aL(G3)]*aL(G4) = [ b*abab | b*(qϕ)*ab ]
b*abab | b*(aϕ)*ab =
= b*abab | b*ϕ*ab =
= b*abab | b*εab =
= b*abab | b*ab =
= b*ab(ab | ε)
L(G) = [b*ab(ab | ε)]
Usuwanie symbolu początkowego z prawych stron produkcji
We : G = <N,T,P,Z> - regularna bez produkcji końcowych
Wy : G’=<N’,T,P’,Z> - bez Z w prawych stronach produkcji
L(G’) = L(G)
Metoda:
P1 := P;
N’ := N;
for (A→ aB) ∈P do
if B=Z then
begin
N’ := N’ ∪ {K};
P1 := P1 – {A → aZ} ∪ {A → aK};
end;
P’ := P1;
for (A → X) ∈P1 and (X = aB or X = ε) do
if A=Z then
P’ := P’ ∪ {K → X};
Przykład :
S → bK
S → bS → S → bK K → bK
S → aA S → aA
S → aB S → aB S → aA
B → bC B → bC K → aA
C → aA C → aA
A → bD A → bD S → aB
D → ε D → ε K→ aB
B → bC
C → aA
A → bD
D → ε
b
a b
S
A
D
a a
b
B
C
a b
S
A
D
b a
K
a a
b
B
C
b
Tw. L1 i L2 – języki regularne generowane przez gramatyki
G1 = <N1,T1,P1,Z1 >
G2 = <N2,T2,P2,Z2 >
Wówczas języki :
(i) L1 ∪ L2
(ii) L1L2 są regularne
(iii) L *
1
Dokonujemy przy założeniach i oznaczeniach :
(1) T = T1 ∪ T2
(2) N1 ∩ N2 = ∅ (jeśli nie, to można nieterminale pomalować na różne kolory)
(3) G1 i G2 - gramatyki regularne bez produkcji końcowych
(4) F1 i F2 - zbiór nieterminalnych symboli końcowych gramatyk G1 i G2
(5) Zbiór symboli końcowych gramatyki G
(i) Konstrukcja G = <N1 ∪ N2 ∪ {Z},T,P,Z > takiej, że L(G) = L1(G1) ∪ L2(G2)
if ε∉L1 ∪ L2 then F:= F1 ∪ F2
else F:= F1 ∪ F2 ∪ {Z};
P:=∅;
for (A → aB) ∈P1 do P:= P ∪ {A → aB};
for (A → aB) ∈P2 do P:= P ∪ {A → aB};
for (Z1 → aB) ∈P1 do P:= P ∪ {Z → aB};
for (Z2 → aB) ∈P2 do P:= P ∪ {Z → aB};
for A ∈ F do P:= P ∪ {A → ε};
a
a
A
* b a
Z
Z1
b b
B
b a
a a
z2
C
b
b
* - Z1 stał się nieosiągalny
(ii)
Konstrukcja G = < N1 ∪ N2 ,T,P,Z1 > takiej, że L(G) = L1(G1)L2(G2)
if Z2 ∉ F2 then F:= F2
else F:= F1 ∪ F1;
P:=∅;
for (A→ aB) ∈P1 and A ∈ N1 – F1 do
P:= P ∪ {A → aB };
for (A→ aB) ∈P1 and A∈ F1 do
P:= P ∪ {A → aB} ∪ {A → bC | (Z2 → bC) ∈P2 };
for (A→ aB) ∈P2 do P:= P ∪ {A → aB};
for A ∈ F do P:= P ∪ {A → ε};
*
A
a
a b b a
b a a
b
Z1
Z2
C
b * b
a
B
* - A i B przestają być symbolami końcowymi
(iii)
Konstrukcja G = < N1 ∪ {Z},T,P,Z > takiej , że : L(G) = [L1(G1)]*
F := F1 ∪ {Z};
P:= ∅;
for a ∈T and A ∈ N1 – F1 do
P := P ∪ {A → aB | (A → aB) ∈ P1};
for a ∈ T and A ∈ F1 do
begin
P := P ∪ {A → aB | (A → aB) ∈ P1};
P := P ∪ {A → aB | (Z1 → aB) ∈ P1};
end;
for a ∈ T do
P := P ∪ {Z1 → aB | (Z → aB) ∈ P1};
for A ∈ F do P := P ∪ {A → ε};
a
d
A
c c
a
c b a b
Z
Z1
b
b
B
Warunek konieczny regularności języka :
Tw. Jeśli L jest językiem regularnym to ∃ k : (w ∈ L ∧ |w| ≥ k) ⇒ (w = xuz ∧ 0 < |u| ≤ k ∧
∀i ≥ 0 : xuiz ∈ L)
w |w| ≥ k
x z
x u z
x ui z
Przykład :
L1 = { aibi : i ≥ 0 } nie jest językiem regularnym (jest bezkontekstowym).
L2 = { abia : i ≥ 0 } jest językiem regularnym opisanym przez wyrażenie regularne ab*a).
Gramatyka prawostronnie regularna (bez produkcji końcowych) jest :
(i) deterministyczna
! (A → aB ) ∈P ∧ (A → aC) ⇒ B = C
(ii) zupełna ! (∀A∈N) (∀a ∈T) (∃(A → aB)∈P) (B∈N)
Tw. Każdą gramatykę regularną można rozszerzyć do gramatyki regularnej i zupełnej
generującej ten sam język.
Tw. (Myhilla) Dla każdej gramatyki regularnej istnieje generująca ten sam język gramatyka deterministyczna i zupełna.
Ze względu na ścisłą odpowiedniość pomiędzy gramatyką prawostronnie regularną (bez
produkcji końcowych) a automatem skończonym wygodnie jest prowadzić wszelkie badania i przekształcenia gramatyk regularnych dotyczące determinizmu i zupełności korzystając z aparatu pojęciowego związanego z automatem skończonym (por. poprzednie wykłady z
przedmiotu: translatory).
Metody definiowania języków regularnych.
(i) wyrażenie regularne
(ii)
gramatyka liniowa lub regularna
(iii) automat
skończony
Konstrukcja automatu skończonego dla gramatyki prawostronnie regularnej (bez produkcji końcowych) :
We : G = <N,T,P,Z> - prawostronnie regularna bez produkcji końcowych
Wy: A = <T,Q,F,qo,δ> - automat skończony taki, że L(A) = L(G)
Q := N;
F := {A ∈ N : (A → ε) ∈ P};
qo := Z;
for (A → aB) ∈P do
zaliczyć B do δ(A,a);