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, 5.11. 2012
1
Příklad
Q = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S A B
aAbBc BB | a AcA I b
£
IB102 Automaty a gramatiky, 5.11.2012
2
Algoritmus pro odstranění -pravidel
Vstup:  CFG Q = (iV, E, P, 5)
Výstup: CFG Q' = (iV, E, P>Sr) bez e-pravidel splňující L{G)=L{Qf)
1 Zkonstruuj N£ = {A G N \ A ^* e}
2 Množinu pravidel P' zkonstruuj takto:
3 foreach A —> X\... Xn £ P do
4 přidej do Pr všechna pravidla tvaru A     a±... an splňující
5 (a) pokud Xi £ N£ pak oli = Xi
6 (b) pokud     G N£ pak a* je bud Xit nebo e
7 (c) ne všechna cti jsou e s od
9 if S G iV£ then přidej do P' pravidla S"    S1 e (S' <£ N U E);
10 N' := N U {S'}
u else N' := JV: S' := 5 fi
IB102 Automaty a gramatiky, 5.11. 2012
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, 5.11.2012
4
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez e-pravidel. Ekvivalence gramatik.
IB102 Automaty a gramatiky, 5.11.2012
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, 5.11.2012
6
Algoritmus pro odstranění jednoduchých pravidel
Vstup:    CFG g = (N, E, P, S) bez e-pravidel
Výstup: CFG Q' = (iV, E, P7, S) bez jednoduchých a e-pravidel, kde
L(G) = L(0')
1 foreach A e N do
2 i := 0;   JVi := {A}
3 repeat i := i + 1
4 Ni := Ni-x U{C\B^CeP,Be iV;_i}
5 until Ni = iVi_i ^    iVA := Nt
7 od
s P' := 0
9 foreach A G iV do
20 p' := p' u {4 u od
S G Na A B —>> a G P není jednoduché}
IB102 Automaty a gramatiky, 5.11. 2012
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, 5.11.2012
8
Korektnost algoritmu
Konečnost.
Výsledná gramatika neobsahuje jednoduchá pravidla.
Ekvivalence gramatik:
L{Qr) C L{Q)  Necht w £ L(Qf), pak existuje derivace
S = ao =>g/ a± =>g/ ... =>gr an = w.
Pokud bylo při kroku olí =>gi ai+i 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     =^>* a^+i. L(C?) C Necht w G pak existuje levá derivace
S = ao ^>g ol\ ^>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, 5.11. 2012
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 bezkontextovému 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, 5.11. 2012
10
Chomského normální forma
Definice 3.19.       Bezkontextová gramatika Q — (iV, E, P, 5) je
dá f
v Chomského normální formě (CNF) <=k> Q je bez e-praviaei a každé pravidlo z P má jeden z těchto tvarů:
1. A -> PC, kde B,C eN
2. A -> a, kde a G S
3.
Věta 3.21. Každý bez kontextový jazyk lze generovat bez kontextovo u gramatikou v Chomského normální formě.
IB102 Automaty a gramatiky, 5.11. 2012
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, 5.11.2012
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 olXß\ol2
aißra2}
PakL(£) = L(g').
IB102 Automaty a gramatiky, 5.11. 2012
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, 5.11. 2012
14
Lemma o vkládání pro bezkontextové jazyky
Věta 3.24. Necht L je CFL. Pak existují G 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 5.11. 2012
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ž 2/c_1 má cestu délky alespoň k. Tato cesta obsahuje alespoň k + 1 neterminálů.
IB102 Automaty a gramatiky, 5.11. 2012
16
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Necht L generován gramatikou Q = (iV,       S), která je v CNF. Označme k = card(N) a položme p = 2/c_1, g = 2k.
Necht 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 Tav něm (libovolnou) nejdelší cestu C.
IB102 Automaty a gramatiky, 5.11. 2012
17
Na cestě C lze zvolit tři uzly ui,u2,us s vlastnostmi:
1. uzly ui,u2 jsou označeny týmž neterminálem, řekněme A,
2. u\ leží blíže ke kořenu než u2,
3. us je list a
4. cesta z u\ do ^3 má délku nejvýše k.
IB102 Automaty a gramatiky, 5.11.2012
18
IB102 Automaty a gramatiky, 5.11. 2012
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 £ 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 < n
4. existuje i £ No takové, že uvlwxly tfL L.
IB102 Automaty a gramatiky, 5.11. 2012
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   mra I < n
4. existuje i £ Nq takové, že uvlwxly tfL L
> L není CFL
IB102 Automaty a gramatiky, 5.11. 2012
21