e-pravidla
Definice 3.13. Řekneme, že CFG G = (N, S, P, S) je bez e-pravidel prave když bud
1. P neobsahuje žadne e-pravidlo (tj. pravidlo tvaru A — e ) nebo
2. v P existuje prave jedno e-pravidlo S — e a S se nevyskytuje na prave strane žadneho pravidla ž P.
IB102 Automaty a gramatiky, 8.11.2010
1
Příklad
Q = ({S, A, B}, (a, b, c}, P, S), kde P obsahuje pravidla
S —» aAbBc
A — BB | a | s
B — AcA | b
IB102 Automaty a gramatiky, 8.11.2010
2
Algoritmus pro odstranění -pravidel
Vstup:  CFG G = (N, S,P,S)
Výstup: CFG G7 = (N7, S, P7, S7) bez e-pravidel splňující L (G )=L(G7)
1 Zkonstruuj N£ = {A G N | A ^* e]
2 MnoZinu pravidel P7 zkonstruuj takto:
3 foreach A — X ... Xn G P do
4 pridej do P7 vsechna pravidla tvaru A — a1... an splňující
5 (a) pokud Xi G N pak ai = Xi
6 (b) pokud Xi G Ne pak ai je buň Xi, nebo e
7 (c) ne vsechna ai jsou e
8 od
9 if S G N then pridej do P7 pravidla S7 — S | e (S7 G N U S);
10 N7 := N U {S7]
11 else N7 := N; S7 := S fi
IB102 Automaty a gramatiky, 8.11.2010
3
Příklad
Q = ({S, A, B}, (a, b, c}, P, S), kde P obsahuje pravidla
S       aAbBc | AB A — BB | a | e
B - AA | b
IB102 Automaty a gramatiky, 8.11.2010
4
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez ^-pravidel. Ekvivalence gramatik.
IB102 Automaty a gramatiky, 8.11.2010
5
Jednoduchá pravidla
Jednoduchým pravidlem nazývame každé pravidlo tvaru A — B, kde
A, B e N.
S — aAbBc
A — aA | B | a
B — bB   | b
IB102 Automaty a gramatiky, 8.11.2010
6
Algoritmus pro odstranění jednoduchých pravidel
Vstup:    CFG G = (N, S, P, S) bez ^-pravidel
Výstup: CFG G' = (N, S, P', S) bez jednoduchých a č-pravidel, kde
L(G) = L(G')
1 foreach A G N do
2 i := 0;  N := {A}
3 repeat i := i + 1
4 Ni := Ni_i U {C | B — C G P, B G N;_i}
5 until N = Ni_1
6 Na := N
7 od
8 P' := 0
9 foreach A G N do
10 P' := P' U {A — a | B G NA A B — a G P není jednoduche}
11 od
IB102 Automaty a gramatiky, 8.11.2010
7
Příklad
G = ({S,A,B,C}, (a,b,c}, P, S), kde P obsahuje pravidla
S — ABC
A — aA | B | a
B — 6B | A
C — cC | A
IB102 Automaty a gramatiky, 8.11.2010
8
Korektnost algoritmu
Konečnost.
Výsledna gramatika neobsahuje jednodučha pravidla.
Ekvivalence gramatik:
L(Gi) C L (G)  Necht w G L(Gi), pak existuje derivace
Pokud bylo pri kroku a =>gi ai+1 použito pravidlo A — /3, pak existuje nejake B G NA takove, že v G platí A =^>* B a B     /3. Tedy v G platí A =>* /3 a a =>* ai+1. L(G) C L(Gi)  Necht w G L(G), pak existuje leva derivace
S = ao =^g ai =^>g ... =^>g an = w.
Tu lže roždelit na úseky tak, že v celem úseku se použila použe jednoducha pravidla anebo žadne jednoduche pravidlo. Úseky s jednoduchíymi pravidly lže nahradit.
IB102 Automaty a gramatiky, 8. 11. 2010
9
Vlastní bezkontextova gramatika
Definice 3.17. CFG Q = (N, Tj,P,S) se nazyva necyklicka, prave když neexistuje A G N takovy, Ze A =^>+ A.
Q se nazyva vlastní, prave když je bez nepoužitelnych symbolU, bez s-pravidel a necyklicka.
Veta 3.18. Ke kazdemu neprazdnemu bezkontextovemu jazyku existuje vlastn í bezkontextova gramatika, ktera jej generuje.
Důkaz. Z bezkontextove gramatiky pro neprázdny jazyk odstraníme s-pravidla a jednoducha pravidla. Odstranením nepouzitelnych symbolu pak získame vlastní gramatiku. □
IB102 Automaty a gramatiky, 8. 11. 2010
10
Chomského normální forma
Definice 3.19. Bežkontextova gramatika G = (N, S, P, S) je v Chomskeho normálni forme (CNF) 4=^> G je bež e-pravidel a každe pravidlo ž P ma jeden ž techto tvaru:
1. A — BC, kde B, C G N
2. A — a, kde a G S
3. S — e
Veta 3.21. Každy bežkontextovy jažyk lže generovat bežkontextovou gramatikou v Chomskeho normalní forme.
IB102 Automaty a gramatiky, 8.11.2010
11
Příklad
Q = ({S,A,B}, (a, b}, P, S), kde P obsahuje pravidla
S -   AS | a
A - AB | AA | a B - b
IB102 Automaty a gramatiky, 8. 11. 2010
12
Lemma o substituci
Lemma 3.20.   (o substituci)
Necht G = (N, T, P, S) je CFG. Necht A — aiBa2 e P. Necht B — Pi | ... | Pr jsou všechna pravidla v P tvaru B — a.
Definujme G' = (N, T, P', S), kde
P' = (P \ {A — aiBa2}) U {A — aipia2 | ... | aiPra2}.
Pak L(G) = L(G7).
IB102 Automatý a gramatiký, B. 11. 2010
13
Algoritmus transformace do CNF
1. L = 0
2. L = 0
Gramatiku pro L převedeme na vlastní a bez jednoduchých pravidel.
X — e X — a X — A X — ab X — aB X — Ab X — AB
X — aBcD
IB102 Automaty a gramatiky, 8. 11. 2010
14
Lemma o vkladaní přo bezkontextové jazyky
Veta 3.24. Necht L je CFL. Pak existují p, q G N (zavisející na L) takova, Ze kaZde slovo z G L delsí neZ p lze psat ve tvaru z = uvwxy,
kde
• alespoň jedno ze slov v, x je neprazdne (tj. vx = e),
• |vwx| < q a
• uv^wx^y G L pro kazde i G N0.
Poznámka 3.25. Tvrzení zustava v platnosti i kdyz namísto konstant p, q budeme vsude psat jen (jedinou) konstantu n.
IB102 Automaty a gramatiky, B. 11. 2010
15
DUkaz Lemmatu o vkladaní pro bezkontextove jazyky
Necht L je generovan gramatikou v CNF.
delka cesty z korene do listu
= poCet modrých hran
= poCet neterminaiu na ceste - 1
hloubka stromu
= maximainí deika cesty
DerivaCní strom hloubky k ma max. 2k listu =>* slovo deiky nejvyse 2k. Derivacn í strom pro slovo dels í neZ 2k-1 ma cestu deiky alespoň k. Tato cesta obsahuje alespoň k + 1 neterminalu.
IB102 Automaty a gramatiky, 8. 11. 2010
16
DUkaz Lemmatu o vkladaní pro bezkontextove jazýký
Necht L generovan gramatikou G = (N, S, P, S), ktera je v CNF. Oznacme k = card(N) a poloZme p = 2k-i, q = 2k.
Necht z G L je slovo delsí neZ p. Pak v libovolnem derivacním stromu slova z existuje cesta delky alespoň k. Zvolme pevne jeden takovy strom T a v nem (libovolnou) nejdelsí cestu C.
IB102 Automaty a gramatiky, 8. 11. 2010
17
Na cestě C lze zvolit tři uzly u1?u2, u3 s vlastnostmi:
1. uzly ui, u2 jsou oznaCeny tymZ neterminalem, řekněme A,
2. u1 lezí blíze ke kořenu nez u2,
3. u3 je list a
4. cesta z u1 do u3 ma delku nejvyse k.
IB102 Automaty a gramatiky, 8.11.2010
18
IB102 Automaty a gramatiky, B. 11. 2010 19
PouZití Lemmatu o vkladaní přo bezkontextove jazyky
Lemma o vkladaní je implikace P =>* Q, kde P je vyrok, ze L je CFL a Q jsou uvedene vlastnosti.
Obmenu Lemmatu o vkladaní —Q —P lze pouzít k dukazu, ze nejaky jazyk L nen í CFL — staCí, kdyz ukazeme platnost —Q.
—Q:
1. Pro libovolnou konstantu n G N
2. existuje slovo z G L delsí nez n takove, ze
3. pro vsechny slova u,v,w,x,y splňující z = uvwxy, vx = e a |vwx| < n
4. existuje i G N0 takove, ze uv^wx^y G L.
IB102 Automaty a gramatiky, 8.11.2010
20
Př íklad poůZit í Lemmatu o vkladan i
L = (aibici | i > 1}
1. Pro libovolnou konstantu n G N
2. existuje slovo z G L delsí nez n takove, ze
3. pro vsechny slova u,v,w,x,y splňující z = uvwxy, vx = s a  |vwx| < n
4. existuje i G N0 takove, ze uviwxiy G L.
L není CFL.
IB102 Automaty a gramatiky, 8. 11. 2010
21