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 bezkontextovou gramatikou.
IB102 Automaty a gramatiky, 31.10. 2011
1
Příklad
g = ({E,T, F], {+,*,(,),i}, P,E), kde P obsahuje pravidla
E T F
E + T T * F (E) |
T F
IB102 Automaty a gramatiky, 31.10. 2011
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,... mají v uspořádání zleva doprava návěští X\,...,     G V, pak
A^X1...XkeP1
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, 31.10. 2011
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, 31.10. 2011
4
Indukční krok k > 1:
(IP) Tvrzení platí pro stromy s nejvýše k — 1 vnitrními uzly. Strom T s k uzly:
• je-li Xi list, označme olí =
• není-li Xi list, pak olí je výsledkem podstromu     s kořenem Xi
• Výsledek T je a±... an.
Platí: =^>* cti    (p^o -^íi které není listem, podle (IP))
A—>Xi... Xn £ P   (z definice deriv. stromu)
Dostá
IB102 Automaty a gramatiky, 31.10. 2011
5
(=^) Necht A       a.   Ukážeme, že v Qa 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 fc krocích, pak v Qb existuje derivační strom s výsledkem /3.
k-\-l k <k
A      a A => Xi... Xn =>► ql\ ... ani kde ^>
Konstrukce stromu s výsledkem a\
□
IB102 Automaty a gramatiky, 31.10. 2011
6
Jednoznačnost derivačních stromů
Derivace je sekvence   S =^> a± =^>     =>> ... =>> an.
Levá (resp. pravá) derivace je taková derivace, kde každé qlí+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, 31.10. 2011
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, 31.10. 2011
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, 31.10. 2011 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 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 (nenormovaný)        neexistuje k; G S*
splňující X =^>* w
X je nepoužitelý typu II (nedosažitelný)       neexistují a, /3 G (iV U S)
splňující S
IB102 Automaty a gramatiky, 31.10. 2011
10
Nalezení nepoužitelných symbolů typu I (neexistuje w G S*: A =>* w)
Vstup:    CFG G = (N, S, P, 5) Výstup:   Ne = {A \ 3w e £*. A w}
1 i := 0; ÍVq := 0
2 repeat i := i + 1
3 Ni := ATi_! U{A \        a e P, ae (iVť_i U E)*}
4 until iVť = iVi_i
5 iVe := JV*
IB102 Automaty a gramatiky, 31.10. 2011
11
Věta. Necht Q = (iV, E, P, S) je CFG taková, že L {Q) ^ 0. Položme G' = (iVe, S, P7,5), kde Pf = P P\ Nex (Ne U S)*. Pak 0' je CFG bez nepoužitelných neterminálů typu I a L(É/) = L{Q').
Důkaz. Dokážeme ÍGÍVe 3w G S*.A ^* w.
(=>) Indukcí k i dokážeme A G iV; 3w G S*. A =^>* w
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 Ni.   Tvrzení plyne z (IP).
• A G Ni+i \ iNrV   Pak existuje A    Xi... Xk G P, kde každé X j je terminál nebo neterminál patřící do A^. Podle (IP) existuje Wj tak, že X j =^>* Wy.
Tedy A =^> Xl... Xk i^i^.-.X/e =^>* ... =^>* w\...Wk, kde wi.. .Wk £ S*.
IB102 Automaty a gramatiky, 31.10. 2011
12
{<=) Indukcí k n dokážeme
A =^> w,w G E* =^> A G Ni pro nějaké i
Základní krok n = 1: A —> w G P okamžitě dává i = 1.
Indukční krok: (IP) Předpokládejme, že dokazované tvrzení platí pro všechna n' < n.
■v Tt | 1 Ti ^ 7
Necht A ^ w.  A => Xi... Xk =>>     kde X,- =j> ^ a     < n. Pokud X j G iV, pak podle (IP) X j G A^. pro nějaké ij. Pokud Xj G S, klademe ij = 0.
Položme i = 1 + max{ii,..., i^}. Pak zřejmě A G A^. □
IB102 Automaty a gramatiky, 31.10. 2011
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. □
IB102 Automaty a gramatiky, 31.10. 2011
14
Nalezení nepoužitelných symbolů typu II (neexistují a, (3 e (N U £)* : S ^* aX/3)
Vstup:    CFG ^ = {N, S, p, 5)
Výstup:   CFG 0' = (AT',    p', S1) bez nedosažitelných symbolů
splňující L(Q) = L{Q')
t i ■= 0; Vť := {S}
2 repeat i := i + 1
3 := Ví_i u {X g Af u E | 3A g       . 4
4 until V* = Vi_i
5 N' := N c\ Ví; E' :=Eí1 vj; P' := p D      x v?)
g p}
Korektnost: leJV'UE' ^> 3a, /3 g (N' U E')* • S aI/3
IB102 Automaty a gramatiky, 31.10. 2011
15
Příklad
Q = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S A B
aSb
dA
eB
c
aB
d
IB102 Automaty a gramatiky, 31.10. 2011
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 Qi).
Krok 2. Z Qi odstraníme symboly typu II (výsledek označme Q2).
IB102 Automaty a gramatiky, 31.10. 2011
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 =>g2 &Xf3
• všechny symboly z Q2 jsou též v Q\
• pro nějaký terminálni řetěz w platí S =^2 aX/3 =>gľ w
• žádný symbol z derivace aXfi =>g w není krokem 2 eliminován a proto aX/3 w
Víme tedy, že existuje derivace S =>g2 aXf3 =>g 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, 31.10. 2011
18