-pravidla
Definice 3.13. Řekneme, že CFG G = (N, , P, S) je bez -pravidel
právě když buď
1. P neobsahuje žádné -pravidlo (tj. pravidlo tvaru A   ) nebo
2. v P existuje právě jedno -pravidlo S   a S se nevyskytuje na
pravé straně žádného pravidla z P.
IB102 Automaty a gramatiky, 3. 11. 2008 1
Příklad
IB102 Automaty a gramatiky, 3. 11. 2008 2
Algoritmus pro odstranění -pravidel
Vstup: CFG G = (N, , P, S)
Výstup: CFG G
= (N
, , P
, S
) bez -pravidel splňující L(G)=L(G
)
1 Zkonstruuj N = {A  N | A 
}
2 Množinu pravidel P
zkonstruuj takto:
3 foreach A  X1 . . . Xn  P do
4 přidej do P
všechna pravidla tvaru A  1 . . . n splňující
5 (a) pokud Xi / N pak i = Xi
6 (b) pokud Xi  N pak i je buď Xi, nebo 
7 (c) ne všechna i jsou 
8 od
9 if S  N then přidej do P
pravidla S
 S |  (S
/ N  );
10 N
:= N  {S
}
11 else N
:= N; S
:= S fi
IB102 Automaty a gramatiky, 3. 11. 2008 3
Příklad
G = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S  aAbBc | AB
A  BB | a | 
B  AA | b
IB102 Automaty a gramatiky, 3. 11. 2008 4
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez -pravidel.
Ekvivalence gramatik.
IB102 Automaty a gramatiky, 3. 11. 2008 5
Jednoduchá pravidla
Jednoduchým pravidlem nazývame každé pravidlo tvaru A  B, kde
A, B  N.
S  aAbBc
A  aA | B | a
B  bB | b
IB102 Automaty a gramatiky, 3. 11. 2008 6
Algoritmus pro odstranění jednoduchých pravidel
Vstup: CFG G = (N, , P, S) bez -pravidel
Výstup: CFG G
= (N, , P
, S) bez jednoduchých a -pravidel, kde
L(G) = L(G
)
1 foreach A  N do
2 i := 0; Ni := {A}
3 repeat i := i + 1
4 Ni := Ni-1  {C | B  C  P, B  Ni-1}
5 until Ni = Ni-1
6 NA := Ni
7 od
8 P
:= 
9 foreach A  N do
10 P
:= P
 {A   | B  NA  B    P není jednoduché}
11 od
IB102 Automaty a gramatiky, 3. 11. 2008 7
Příklad
G = ({S, A, B, C}, {a, b, c}, P, S),
kde P obsahuje pravidla
S  ABC
A  aA | B | a
B  bB | A
C  cC | A
IB102 Automaty a gramatiky, 3. 11. 2008 8
Korektnost algoritmu
Konečnost.
Výsledná gramatika neobsahuje jednoduchá pravidla.
Ekvivalence gramatik:
L(G
)  L(G) Nechť w  L(G
), pak existuje derivace
S = 0 G 1 G . . . G n = w.
Pokud bylo při kroku i G i+1 použito pravidlo A  , pak
existuje nějaké B  NA takové, že v G platí A 
B a B  .
Tedy v G platí A 
 a i 
i+1.
L(G)  L(G
) Nechť wL(G), pak existuje levá derivace
S = 0 G 1 G . . . G n = w.
Tu lze rozdělit na úseky tak, že v celém úseku se použila pouze
jednoduchá pravidla anebo žádné jednoduché pravidlo. Úseky
s jednoduchými pravidly lze nahradit.
IB102 Automaty a gramatiky, 3. 11. 2008 9
Vlastní bezkontextová gramatika
Definice 3.17. CFG G = (N, , P, S) se nazývá necyklická, právě
když neexistuje A  N takový, že A +
A.
G se nazývá vlastní, právě když je bez nepoužitelných symbolů, bez
-pravidel a necyklická.
Věta 3.18. Ke každému neprázdnému bezkontextovému jazyku
existuje vlastní bezkontextová gramatika, která jej generuje.
Důkaz. Bezkontextovou gramatiku pro neprázdný jazyk lze převést na
redukovanou gramatiku, odstranit -pravidla a jednoduchá pravidla. 2
IB102 Automaty a gramatiky, 3. 11. 2008 10
Chomského normální forma
Definice 3.19. Bezkontextová gramatika G = (N, , P, S) je
v Chomského normální formě (CNF)
def
 G je bez -pravidel a
každé pravidlo z P má jeden z těchto tvarů:
1. A  BC, kde B, C  N
2. A  a, kde a  
3. S  
Věta 3.21. Každý bezkontextový jazyk lze generovat bezkontextovou
gramatikou v Chomského normální formě.
IB102 Automaty a gramatiky, 3. 11. 2008 11
Příklad
IB102 Automaty a gramatiky, 3. 11. 2008 12
Lemma o substituci
Lemma 3.20. (o substituci)
Nechť G = (N, , P, S) je CFG. Nechť A  1B2  P.
Nechť B  1 | . . . | r jsou všechna pravidla v P tvaru B  .
Definujme G
= (N, , P
, S), kde
P
= (P {A  1B2})  {A  112 | . . . | 1r2}.
Pak L(G) = L(G
).
IB102 Automaty a gramatiky, 3. 11. 2008 13
Algoritmus transformace do CNF
1. L = 
2. L = 
Gramatiku pro L převedeme na vlastní a bez jednoduchých pravidel.
X  
X  a
X  A
X  ab
X  aB
X  Ab
X  AB
...
X  aBcD
IB102 Automaty a gramatiky, 3. 11. 2008 14
Lemma o vkládání pro bezkontextové jazyky
Věta 3.24. Nechť L je CFL. Pak existují p, q  N (závisející na L)
taková, že každé slovo z  L delší než p lze psát ve tvaru z = uvwxy,
kde
* alespoň jedno ze slov v, x je neprázdné (tj. vx = ),
* |vwx|  q a
* uvi
wxi
y  L pro každé i  N0.
Poznámka 3.25. Tvrzení zůstává v platnosti i když namísto konstant
p, q budeme všude psát jen (jedinou) konstantu n.
IB102 Automaty a gramatiky, 3. 11. 2008 15
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Nechť L je generován gramatikou v CNF.
délka cesty z kořene do listu
= počet modrých hran
= počet neterminálů na cestě - 1
hloubka stromu
= maximální délka cesty
Derivační strom hloubky k má max. 2k
listů = slovo délky nejvýše 2k
.
Derivační strom pro slovo delší než 2k-1
má cestu délky alespoň k.
Tato cesta obsahuje alespoň k + 1 neterminálů.
IB102 Automaty a gramatiky, 3. 11. 2008 16
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Nechť L generován gramatikou G = (N, , P, S), která je v CNF.
Označme k = card(N) a položme p = 2k-1
, q = 2k
.
Nechť z  L je slovo delší než p. Pak v libovolném derivačním stromu
slova z existuje cesta délky alespoň k. Zvolme pevně jeden takový
strom T a v něm (libovolnou) nejdelší cestu C.
IB102 Automaty a gramatiky, 3. 11. 2008 17
Na cestě C lze zvolit tři uzly u1, u2, u3 s vlastnostmi:
1. uzly u1, u2 jsou označeny týmž neterminálem, řekněme A,
2. u1 leží blíže ke kořenu než u2,
3. u3 je list a
4. cesta z u1 do u3 má délku nejvýše k.
IB102 Automaty a gramatiky, 3. 11. 2008 18
IB102 Automaty a gramatiky, 3. 11. 2008 19
Použití Lemmatu o vkládání pro bezkontextové jazyky
Lemma o vkládání je implikace P = Q, kde P je výrok, že L je CFL
a Q jsou uvedené vlastnosti.
Obměnu Lemmatu o vkládání Q = P lze použít k důkazu, že
nějaký jazyk L není CFL -- stačí, když ukážeme platnost Q.
Q:
1. Pro libovolnou konstantu n  N
2. existuje slovo z  L delší než n takové, že
3. pro všechny slova u, v, w, x, y splňující
z = uvwxy, vx =  a |vwx|  n
4. existuje i  N0 takové, že uvi
wxi
y  L.
IB102 Automaty a gramatiky, 3. 11. 2008 20
Příklad použití Lemmatu o vkládání
L = {ai
bi
ci
| i  1}
1. Pro libovolnou konstantu n  N
2. existuje slovo z  L delší než n takové, že
3. pro všechny slova u, v, w, x, y splňující
z = uvwxy, vx =  a |vwx|  n
4. existuje i  N0 takové, že uvi
wxi
y  L.
= L není CFL.
IB102 Automaty a gramatiky, 3. 11. 2008 21