Kanonické tvary bezkontextových gramatik
• redukované bezkontextové gramatiky
• gramatiky bez e-pravidel
• gramatiky bez jednoduchých pravidel
• gramatiky bez levé rekurze
• Chomského normální forma
• Greibachové normální forma
IB102 Automaty, gramatiky a složitost, 21.10. 2013 1
Redukované bezkontextové gramatiky
Definice 3.7      Symbol X £ N U S je nepoužitelný v CFG Q —
(iV, S, P, S) právě když v C/ neexistuje derivace tvaru
S =^>* wXy =^>* w.x?/
pro žádné w,x,y G S*. Řekneme, že Q je redukovaná, jestliže neobsahuje žádné nepoužitelné symboly.
X je nepoužitelý typu I neexistuje k; G S*
(tj. nenormovaný) splňující X =^>* w
	
<	>
	/
	\
<	>
	
(tj. nedosažitelný)        splňující 5 =^>*
IB102 Automaty, gramatiky a složitost, 21.10.2013
2
Nalezení nepoužitelných symbolů typu I (neexistuje w G £*: A =>* w)
Vstup:    CFG g = (N, E, P, S)
Výstup:   Ne = {A \ 3w E S*. A =^>* w} (normované neterminály)
1 i := 0; No := 0
2 repeat i := i + 1
3 Ni := iVi U {i | i ^ a G P, a e (A^i U £)*}
4 until iVť = iVť_i
5 iVe := Ni
IB102 Automaty, gramatiky a složitost, 21.10.2013
3
Korektnost algoritmu
Konečnost.
Správnost výsledku: Dokážeme A G Ne <=^> 3w G E*. A =^>* w (=>) Indukcí k i dokážeme A e Ni 3w G £*. A ^* ty.
Základní krok i = 0: Platí triviálně, protože Nq = 0.
Indukční krok: (IP) Tvrzení platí pro i. Dokážeme pro i + 1.
• A G Ni.   Tvrzení plyne z (IP).
• A G iVi+i \ Ni.   Pak existuje i ^ Ji... Ifc G P, kde každé Xj je terminál nebo neterminál patřící do Ni. Podle (IP) existuje Wj tak, že Xj =^>*
Tedy A X\...Xk =^>* wiX2... Xk =^>* ... =^>* . kde wi.. .wj- £ S*.
IB102 Automaty, gramatiky a složitost, 21.10.2013
{<=) Indukcí k n dokážeme
A^w^weY,* =^> A G Ni pro nějaké i.
Základní krok n = 1: i^ioGP okamžitě dává i = 1.
Indukční krok: (IP) Předpokládejme, že dokazované tvrzení platí pro všechna n! < n.
Necht A =^> w.  A => Xi... X^ => w, kde X j =$> Wj a rij < n. Pokud X j G N, pak podle (IP) X j G Ni. pro nějaké ij. Pokud Xj G E, klademe ij = 0.
Položme i = 1 + max{ii,..., i^}. Pak zřejmě A G A^.
IB102 Automaty, gramatiky a složitost, 21.10.2013
5
Důsledek 3.10. Existuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L(Q) = 0.
Důkaz. Stačí ověřit, zda S ^ Ne. □
Věta. Necht Q = (N,E,P,S) je CFG taková, že L{Q) ŕ 0. Pak existuje ekvivalentní CFG Q1 bez nepoužitelných neterminálů typu I.
Důkaz. Stačí spočítat množinu Ne a položit Q' = (JVe, E, P', 5), kde
p; = pn JVex (7VeuE)*. □
IB102 Automaty, gramatiky a složitost, 21.10.2013
6
Nalezení nepoužitelných symbolů typu II (neexistují a,/3 6 (NU £)* : S ^* aX/3)
Vstup:    CFG Q = (N, E, P, S)
Výstup:   CFG Q' = (N',Y,',P',S) bez nedosažitelných symbolů
splňující L(Q) = L(Q')
1 i ■= 0; Ví := {S}
2 repeat i := i + 1
3 Ví :=Vi-!U{Xe iVUS I 3AeVi-x.A
4 until Ví = Ví_i
5 N' := N Cl      S' :=Sn VJ; P':=Pfl      x V*)
a'xp' e P}
Korektnost: X £ N' U E' 3a, /3 e (iV7 U E')* • 5 ^* aXp
IB102 Automaty, gramatiky a složitost, 21.10.2013
7
Příklad
Q = ({S, A, B}, {a, b, c, d, e}, P, S), kde P obsahuje pravidla
S A B
aSb
dA
eB
c
aB
d
IB102 Automaty, gramatiky a složitost, 21.10.2013
8
Eliminace nepoužitelných symbolů
Věta 3.11. Každý neprázdný bezkontextový jazyk L je generován nějakou redukovanou CFG.
Důkaz. Necht L je generován nějakou CFG Q.
Krok 1. Z Q odstraníme symboly typu I (výsledek označme Qi).
Krok 2. Z Qi odstraníme symboly typu II (výsledek označme Q2).
IB102 Automaty, gramatiky a složitost, 21.10.2013
9
Korektnost: Sporem dokážeme, že Q2 je redukovaná CFG. Předpokládejme, že Q2 má nepoužitelný symbol X.
• v Q2 existuje derivace S ^g2 olX(3
• všechny symboly z Q2 jsou též v Q\
• pro nějaký terminálni řetěz w platí S ^g2 ctX/3 u>
• žádný symbol z derivace w není krokem 2 eliminován a proto ii;
Víme tedy, že existuje derivace S =>g2 aXf3 w, kde w je terminálni řetěz. To je ve sporu s předpokladem, že X je v Q2 nepoužitelný. □
IB102 Automaty, gramatiky a složitost, 21.10.2013
10
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, gramatiky a složitost, 21.10.2013
11
Příklad
Q = ({S, A, P}, {a, 6, c}, P, S), kde P obsahuje pravidla
S -> aAbBc
A ^ BB B -> Ac4
IB102 Automaty, gramatiky a složitost, 21.10.2013
12
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 ATe 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, gramatiky a složitost, 21.10.2013
13
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, gramatiky a složitost, 21.10.2013
14
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez e-pravidel. Ekvivalence gramatik.
IB102 Automaty, gramatiky a složitost, 21.10.2013
15
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, gramatiky a složitost, 21.10.2013
16
Algoritmus pro odstranění jednoduchých pravidel
Vstup:    CFG Q = (iV, E, P, 5) bez ^-pravidel
Výstup: CFG C/' = (iV, E, P', 5) bez jednoduchých a e-pravidel, kde
= L(Qf)
1 foreach A e N do
2 i := 0;  iVi := {A}
3 repeat i := i + 1
4 iVi := iVi_i U{C|P^CgP,PG íVí-i}
5 until JVť = iV;_i
z od
a P' := 0
9 foreach iGiVdo
20 p' := p' u {A a I B G ÍVa A B a G P není jednoduché} u od
IB102 Automaty, gramatiky a složitost, 21.10.2013
17
Příklad
Q = ({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, gramatiky a složitost, 21.10.2013
18
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{Q) 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, gramatiky a složitost, 21.10.2013
19
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.
Q 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, gramatiky a složitost, 21.10.2013
20
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, gramatiky a složitost, 21.10.2013
21
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, gramatiky a složitost, 21.10.2013
22
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, gramatiky a složitost, 21.10.2013
23
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/J
IB102 Automaty, gramatiky a složitost, 21.10.2013
24
Lemma o vkládání pro bezkontextové jazyky
Věta 3.24. Necht L je CFL. Pak existují p, q G N (závisející na Ľ) taková, že každé slovo z G 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 Nq
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, gramatiky a složitost, 21.10.2013
25
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, gramatiky a složitost, 21.10.2013
26
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, gramatiky a složitost, 21.10.2013
27
Na cestě C lze zvolit tři uzly ui,U2,u% s vlastnostmi:
1. uzly u\,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 us má délku nejvýše k.
IB102 Automaty, gramatiky a složitost, 21.10.2013
28
IB102 Automaty, gramatiky a složitost, 21.10.2013
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 G No takové, že uvlwxly tfL L.
IB102 Automaty, gramatiky a složitost, 21.10.2013
30
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, gramatiky a složitost, 21.10.2013
31