5-pravidla
Definice 3.13.   Řekneme, že CFG Q = (iV, E, P, 5) je bez e-pravidel
právě když bud
1. P neobsahuje žádné e-pravidlo (tj. pravidlo tvaru A —t e ) nebo
2. v P existuje právě jedno e-pravidlo S     e a S se nevyskytuje na pravé straně žádného pravidla z P.
IB102 Automaty a gramatiky, 7.11. 2011
1
Příklad
Q = ({S, A, £>}, {a, 6, c}, P, S), kde P obsahuje pravidla
S -> aAbBc
A ^ BB B -> Ac4
IB102 Automaty a gramatiky, 7.11. 2011
2
Algoritmus pro odstranění -pravidel
Vstup:  CFG Q = (iV, E, P, 5)
Výstup: CFG Q' = (iV, E, P', S') bez e-pravidel splňující L{G)=L{Q')
1 Zkonstruuj N£ = {A <E N \ A =^>* e}
2 Množinu pravidel P' zkonstruuj takto:
3 foreach A —± X\... Xn £ P do
4 přidej do P' všechna pravidla tvaru A—^a\...an splňující
5 (a) pokud Xi £ N£ pak olí = Xi
6 (b) pokud Xi G iVe pak    je bud Xit nebo e
7 (c) ne všechna    jsou e s od
9 if S G iVe then přidej do P' pravidla S"    S1 e (S" £ JV U E);
10 N' := N U {S'}
u else JV' := N; S' := 5 fi
IB102 Automaty a gramatiky, 7.11. 2011
3
Příklad
Q = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S A B
aAbBc BB | a AA I b
AB
e
IB102 Automaty a gramatiky, 7.11.2011
4
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez e-pravidel. Ekvivalence gramatik.
IB102 Automaty a gramatiky, 7.11. 2011
5
Jednoduchá pravidla
Jednoduchým pravidlem nazývame každé pravidlo tvaru A —>■ B, kde
A, B e N.
S A B
aAbBc aA | B bB   I b
a
IB102 Automaty a gramatiky, 7.11.2011
6
Algoritmus pro odstranění jednoduchých pravidel
Vstup:   CFG Q = (N, Ľ, P, S) bez e-pravidel
Výstup: CFG Q' = (N,T,,P',S) bez jednoduchých a £-pravidel, kde
L{Q) = L{Q')
1 foreach A G N do
2 i := 0;  Ni := {A}
3 repeat i := i + 1
4 Ni := iVi_i U{C\B^CeP,Be JVť_i} s       until iVť = iVj_i
6    iVA := JVť ľ od
s P' := 0
e foreach A G AT do
io P' := P' U {A -> a I B <E NA A B -> a G P není jednoduché} u od
IB102 Automaty a gramatiky, 7.11.2011
7
Příklad
g = ({S,A,B,C},{a,b,c},P,S), kde P obsahuje pravidla
S A B
C
ABC aA | B bB | A cC A
a
IB102 Automaty a gramatiky, 7.11.2011
8
Korektnost algoritmu
Konečnost.
Výsledná gramatika neobsahuje jednoduchá pravidla.
Ekvivalence gramatik:
L(Q') C L (Q)  Necht w G L(Qf), pak existuje derivace
S = a0 ^>qi ol\ ^>qi ... ^>qi an = w.
Pokud bylo při kroku olí ^g* &í+\ použito pravidlo A —> fi, pak existuje nějaké B G Na takové, že v Q platí A =^>* B a B —> /3. Tedy v Q platí A =^>* /3 a olí =^>* a^+i. L(C?) C Necht u> G pak existuje levá derivace
S — ao ^g di ^g . . . ^g an = 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, 7.11. 2011
9
Vlastní bezkontextová gramatika
Definice 3.17. CFG Q = (iV, S) se nazývá necyklická, právě když neexistuje A e N takový, že A =^>+ A.
se nazývá vlastní, právě když je bez nepoužitelných symbolů, bez e-pravidel a necyklická.
Věta 3.18. Ke každému neprázdnému bez kontextové m u jazyku existuje vlastní bezkontextová gramatika, která jej generuje.
Důkaz. Z bezkontextové gramatiky pro neprázdný jazyk odstraníme e-pravidla a jednoduchá pravidla. Odstraněním nepoužitelných symbolů pak získáme vlastní gramatiku. □
IB102 Automaty a gramatiky, 7.11. 2011
10
Chomského normální forma
Definice 3.19.       Bezkontextová gramatika Q — (iV,       S) je
dá f
v Chomského normální formě (CNF) <=^> Q je bez e-praviaei a každé pravidlo z P má jeden z těchto tvarů:
1. A -> BC, kde B,C eN
2. A -> a, kde a G S
3.
Věta 3.21. Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Chomského normální formě.
IB102 Automaty a gramatiky, 7.11. 2011
11
Příklad
g = ({S,A,B},{a,b},P,S), kde P obsahuje pravidla
S A B
AS AB b
a
AA
a
IB102 Automaty a gramatiky, 7.11.2011
12
Lemma o substituci
Lemma 3.20.   (o substituci)
Necht G = (N, E, P, S) je CFG. Necht A -> aľBa2 G P. Necht B —> fii I ... I (3r jsou všechna pravidla v P tvaru B
a,
Definujme Q' = (N, E, P', 5), kde
P' = (P \ {A     aiPa2}) U {A -> axß\Oi2
a±ßra2}
Pak L(G) = L(0')
IB102 Automaty a gramatiky, 7.11. 2011
13
Algoritmus transformace do CNF
1. L = 0
2.
Gramatiku pro L převedeme na vlastnia bez jednoduchých pravidel.
X ->• s
X ->■ a
X ->• A
X ->■ ab
X ^ aB
X ^ Ab
X ^ AB
X -»• aScĽ
IB102 Automaty a gramatiky, 7.11. 2011
14
Lemma o vkládání pro bezkontextové jazyky
Věta 3.24. Necht L je CFL. Pak existují p, q £ N (závisející na Ľ) 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 ^ e)}
vwx
< q a
uvlwxly G L pro každé i G No
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, 7.11. 2011
15
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Necht 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~ľ má cestu délky alespoň k. Tato cesta obsahuje alespoň k + 1 neterminálů.
IB102 Automaty a gramatiky, 7.11. 2011
16
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Necht L generován gramatikou Q = (iV, S, P, S), která je v CNF. Označme k = card(N) a položme p = 2/c_1ř g = 2fe.
Necht z G 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 Tav něm (libovolnou) nejdelší cestu C.
IB102 Automaty a gramatiky, 7.11. 2011
17
Na cestě C lze zvolit tři uzly ^1,^25^3 s vlastnostmi:
1. uzly 1/1,1x2 jsou označeny týmž neterminálem, řekněme A,
2. u\ leží blíže ke kořenu než u2l
3. 1x3 je list a
4. cesta z u\ do 1x3 má délku nejvýše k.
IB102 Automaty a gramatiky, 7.11. 2011
18
IB102 Automaty a gramatiky, 7.11. 2011
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í -iQ -iP lze použít k důkazu, že nějaký jazyk L není CFL — stačí, když ukážeme platnost -iQ.
1. Pro libovolnou konstantu n G N
2. existuje slovo z G L delší než n takové, že
3. pro všechny slova u,v,w,x,y splňující z = uvwxy, vx    £ a < n
4. existuje i G No takové, že uvlwxly tfL L.
IB102 Automaty a gramatiky, 7.11. 2011
20
Příklad použití Lemmatu o vkládání
L = {aW | 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 ^ e a   iru;:r| < n
4. existuje i G No takové, že uvlwxly tfL L
> L není CFL
IB102 Automaty a gramatiky, 7.11. 2011
21