Bezkontextové jazyky
Bezkontextová gramatika (context-free grammar,  CFG) Q je
čtveřice (iV, E, P, S), kde
• N je neprázdná konečná množina neterminálních symbolů,
• S je konečná množina terminálních symbolů taková, že N n S = 0 (značení: y = JVUE),
• S G N je počáteční neterminál,
• P C iV x y* je konečná množina pravidel.
Jazyk je bezkontextový, pokud je generovaný nějakou bez kontextovo u gramatikou.
IB102 Automaty a gramatiky, 29.10. 2012
1
Příklad
Q = ({E,T,F},{+,*,(,),i},P,E), kde P obsahuje pravidla
E T F
E + T T * F
(E) |
T F
IB102 Automaty a gramatiky, 29.10. 2012
2
Derivační stromy pro bezkontextové gramatiky
Definice 3.1.     Necht Q = (N, E, P, S) je CFG. Strom T nazveme derivačním stromem v Q právě když
1. kořen má návěští S, vnitřní uzly mají návěští z N, listy mají návěští
z iVUSU{e}ř
2. má-li vnitřní uzel návěští A a jeho všichni synové ni,..., n& mají v uspořádání zleva doprava návěští Xj.,...,     G V, pak
3. každý list s návěštím e je jediným synem svého otce.
Výsledkem derivačního stromu T nazveme slovo vzniklé zřetězením návěští listů v uspořádání zleva doprava.
IB102 Automaty a gramatiky, 29.10. 2012
3
Vztah mezi derivačními stromy a relací =^>
Věta 3.3. Necht Q = (iV, E, P, S) je CFG. Pak pro libovolné
a £ (N U S)* platí S =^>* a právě když v Q existuje derivační strom s výsledkem a.
Důkaz. Označme Q a — (iV, E, P, A), kde A e N. Dokážeme, že pro každé A e N platí
A =^>* a v Q a existuje derivační strom s výsledkem a
(^=) Necht a je výsledkem derivačního stromu, který má k vnitřích uzlů. Indukcí vzhledem ke k ukážeme, že pak A =^>* a. Základní krok k — 1:
IB102 Automaty a gramatiky, 29.10. 2012
4
Indukční krok k > 1:
(IP) Tvrzení platí pro stromy s nejvýše k — Strom T s k uzly:
1 vnitřními uzly.
• je-li Xi list, označme olí = Xi
• není-li Xi list, pak cti je výsledkem podstromu Ti s kořenem Xi
• Výsledek T je ai... an.
Platí: =^>* q>í    (pro X^, které není listem, podle (IP))
A —> Xi... Xn G P   (z definice deriv. stromu)
Dostáváme A     X\... Xn =^>* a\... an.
IB102 Automaty a gramatiky, 29.10. 2012
5
(=^) Necht A =^>* a.   Ukážeme, že v Q a existuje derivační strom s výsledkem a. Použijeme indukci k délce odvození A =^>* a.
Základní krok A 4> a: Pak a = A a odpovídající derivační strom má jen jeden uzel (kořen je list) s označením A.
Indukční krok A      a, k > 0:
(IP) Pro každé B G N platí: pokud B =^>* (3 v nejvýše k krocích, pak v Q b existuje derivační strom s výsledkem f3.
k-\-l k <k
A =^> a     =^>     A => Xi... Xn =^> ai... ani kde Xi ^> olí Konstrukce stromu s výsledkem a:
□
IB102 Automaty a gramatiky, 29.10. 2012
6
Jednoznačnost derivačních stromů
Derivace je sekvence   S =^> a\ =>> ... =>> an-
Levá (resp. pravá) derivace je taková derivace, kde každé a^+i vznikne z     přepsáním nejlevějšího (resp. nej pravějšího) neterminálu.
Každému derivačnímu stromu odpovídá jediná levá derivace. Každé levé derivaci odpovídá jediný derivační strom.
Analogicky pro pravou derivaci.
Existuje pro každé w £ L{Q) právě jeden derivační strom?
IB102 Automaty a gramatiky, 29.10. 2012
7
Definice 3.7. CFG Q se nazývá víceznačná (nejednoznačná) právě když existuje w £ L{Q) mající alespoň dva různé derivační stromy.
V opačném případě říkáme, že Q je jednoznačná.
Bezkontextový jazyk L se nazývá vnitřně (inherentně) víceznačný,
právě když každá bezkontextová gramatika, která jej generuje, je víceznačná.
IB102 Automaty a gramatiky, 29.10. 2012
8
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 a gramatiky, 29.10. 2012 9
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 Q neexistuje derivace tvaru
S =^>* wXy =^>* wxy
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 a gramatiky, 29.10. 2012
10
Nalezení nepoužitelných symbolů typu I (neexistuje w € >ľ:: A =>* w)
Vstup:    CFG Q = (N, E, P, S)
Výstup:   Ne = {A \ 3w & E*. A =4>* w} (normované neterminály)
1 i := 0; N0 := 0
2 repeat i := i + 1
3 JVť := JV;_i U {A | A ^ a (E P, a G (JVť_i U E)*}
4 until iVť = Ni-i
5 iVe := iVť
IB102 Automaty a gramatiky, 29.10. 2012
11
Korektnost algoritmu
Konečnost.
Správnost výsledku: Dokážeme A G Ne <=^> 3w G E*. A =^>* w (=>) Indukcí k i dokážeme A G Ni 3w G £*. A ^* ty.
Základní krok i = 0: Platí triviálně, protože ÍVq = 0.
Indukční krok: (IP) Tvrzení platí pro i. Dokážeme pro i + 1.
• A G A^.   Tvrzení plyne z (IP).
• A G iVi+i \ iVi.   Pak existuje A ^ Xľ... Xk e P, kde každé Xj je terminál nebo neterminál patřící do Ni. Podle (IP) existuje Wj tak, že     =^>* w^.
Tedy A =^> Xľ.. ,Xk =^>* wiX2 ... Xk =^>* ... =^>* wi. kde wi.. .wk G S*.
IB102 Automaty a gramatiky, 29.10. 2012
{<=) Indukcí k n dokážeme
A     w,w G E* =^> A G Ni pro nějaké i.
Základní krok n = 1: A ^ w e P okamžitě dává i = 1.
Indukční krok: (IP) Předpokládejme, že dokazované tvrzení platí pro všechna n' < n.
Necht A =^> ty.  A =^> Xi... Xk => w, kde X j     ^ a     < n. Pokud X j G iV, pak podle (IP)      G iV^. pro nějaké i j. Pokud Xj G S, klademe i, = 0.
Položme i — 1 + max{ii,..., i/c}. Pak zřejmě A G A^.
IB102 Automaty a gramatiky, 29.10. 2012
13
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 Q' bez nepoužitelných neterminálů typu I.
Důkaz. Stačí spočítat množinu Ne a položit Q' = (Ne, E, P', S), kde
P' = p n Ne x (iVeUE)*. □
IB102 Automaty a gramatiky, 29.10.2012
14
Nalezení nepoužitelných symbolů typu II (neexistují a,fte (N U £)* : S aX/3)
Vstup:    CFG Q = (N, S1)
Výstup:   CFG Q' = (N',T,',P',S) bez nedosažitelných symbolů
splňující L(C?) = L(G')
t i ■= 0; Vť := {,5}
2 repeat i := i + 1
3 Ví := Vi-x U {X G AT US | 3A G Ví-!. A
4 until Ví = Ví-!
5 N' := N (1 Ví; S' :=Síl V; P' := P í~l      x V™)
a'X/3' G P}
Korektnost: leJV'US' <^ 3a,/5 G (N' U £')* • «5 ^*
IB102 Automaty a gramatiky, 29.10. 2012
15
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 a gramatiky, 29.10. 2012
16
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 Q\).
Krok 2. Z Qi odstraníme symboly typu II (výsledek označme Q2).
IB102 Automaty a gramatiky, 29.10. 2012
17
Korektnost: Sporem dokážeme, že Q2 je redukovaná CFG. Předpokládejme, že Q2 má nepoužitelný symbol X.
• v Q2 existuje derivace S =>g aX/3
• všechny symboly z Q2 jsou též v Q\
• pro nějaký terminálni řetěz w platí S =>g2 cxXfi =>gľ w
• žádný symbol z derivace aX/3 =>g w není krokem 2 eliminován a proto =>g n;
Víme tedy, že existuje derivace S =>g aXfi =>g2 w, kde w je terminálni řetěz. To je ve sporu s předpokladem, že X je v Q2 nepoužitelný. □
IB102 Automaty a gramatiky, 29.10. 2012
18