Bezkontextové jazyky
Bezkontextová gramatika (context-free grammar, CFG) Q je čtveřice (A/,I,P, S), kde
■ N je neprázdná konečná množina neterminálních symbolů,
■ Z je konečná množina terminálních symbolů taková, že N n Z = 0 (značení: V = Nu Z),
■ S g A/ je počáteční neterminál,
■ P c A/ x V* je konečná množina pravidel.
Jazyk je bezkontextový, pokud je generovaný nějakou bezkontextovou gramatikou.
IB102 Automaty a gramatiky, 29.10.2018
1/18
Příklad
G = {{E, T, F}, {+, *, (,), /'}, P, E), kde P obsahuje pravidla
£ ^ £+ľ | T T      T* F | F F      (E) | /
IB102 Automaty a gramatiky, 29.10.2018
2/18
Derivační stromy pro bezkontextové gramatiky
Definice 3.1. Nechť Q = (A/, Z, P, S) je CFG.
Strom 7 nazveme derivačním stromem v Q právě když
Q kořen má návěští S, vnitřní uzly mají návěští z A/, listy mají návěští
z A/u Z u {e},
B má-li vnitřní uzel návěští A a jeho všichni synové n-i,..., %
mají v uspořádání zleva doprava návěští X1,..., Xk e N u Z u {^}5 pak >A    X| ... X/c g P,
B každý list s návěštím s 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.2018
3/18
Vztah mezi derivačními stromy a relací =
Věta 3.3. Nechť q = (A/, Z, P, S) je CFG. Pak pro libovolné a e {Nu Z)* platí S     a právě když v q existuje derivační strom s výsledkem a.
def
Důkaz. Označme q a = (A/, 51, P, /A), kde A e N. Dokážeme, že pro každé A e N platí
A =4>* a <=^>   v     existuje derivační strom s výsledkem a
(<==) Nechť a je výsledkem derivačního stromu, který má k vnitřích uzlů. Indukcí vzhledem ke k ukážeme, že pak A =4>* a. Základní krok k = 1:
IB102 Automaty a gramatiky, 29.10.2018
4/18
Indukční krok k > 1:
(IP) Tvrzení platí pro stromy s nejvýše k - 1 vnitřními uzly. Strom T s k uzly:
■ je-li Xj list, označme a-, = X,
■ není-li X, list, pak a-, je výsledkem podstromu T, s kořenem X,
■ výsledek T je
Platí:   Xj =4>* a,-   (pro Xj, které není listem, podle (IP))
A -> X1 ... Xn g P (z definice derivačního stromu)
Dostáváme /4 =4> X1 ... Xn =4>*
IB102 Automaty a gramatiky, 29.10.2018
5/18
(=;>) Nechť 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 e N platí: pokud B =>* (3 v nejvýše k krocích, pak v QB existuje derivační strom s výsledkem (3.
A      a A =4> Xi ... Xn    a-\ ... an, kde X, ^> a/
Konstrukce stromu s výsledkem a:
IB102 Automaty a gramatiky, 29.10.2018
□
6/18
Jednoznačnost derivačních stromů
Derivace je sekvence S =4> a1    a2    ... an.
Levá (resp. pravá) derivace je taková derivace, kde každé vznikne z a/ přepsáním nejlevějšího (resp. nejpravě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 e L(q) právě jeden derivační strom?
IB102 Automaty a gramatiky, 29.10.2018
7/18
Definice 3.5. CFG q se nazývá víceznačná (nejednoznačná) právě když existuje w e 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.2018
8/18
Kanonické tvary bezkontextových gramatik
■ redukované bezkontextové gramatiky
■ gramatiky bez ^-pravidel
■ gramatiky bez jednoduchých pravidel
■ vlastní gramatiky
■ Chomského normálni forma
■ gramatiky bez levé rekurze
■ Greibachové normální forma
IB102 Automaty a gramatiky, 29.10.2018
9/18
Redukované bezkontextové gramatiky
Definice 3.7. Symbol X e N u Z je nepoužitelný v CFG q = (A/, Z, P, právě když v q neexistuje derivace tvaru
S =4>* wXy =4>* wxy
pro žádné w,x,y e Z*. Řekneme, že c? je redukovaná, jestliže neobsahuje žádné nepoužitelné symboly.
X je nepoužitelný typu I <=^> neexistuje i^Gľ (tj. nenormovaný) splňující X =4>* w
X je nepoužitelný typu II <=^> neexistují a, p e (A/ u Z)* (tj. nedosažitelný) splňující S =4>*
IB102 Automaty a gramatiky, 29.10.2018
Nalezení nepoužitelných symbolů typu I (neexistuje w eZ*: A^>* w)
Vstup:   CFG q = (N, Z, P, S)
Výstup: Ne = {A \ 3w e E*. A =^>* w} (normované neterminály)
1: / :=0; A/0 := 0
2: repeat
3:      / := /' + 1
4:      A// := /V,_-| u{/A|/A^oeP, a e (A/,_-| u Z)*} 5: until A// = A//_i 6: A/e := A//
IB102 Automaty a gramatiky, 29.10.2018 11/18
Korektnost algoritmu
Konečnost.
Správnost výsledku: Dokážeme A e Ne <=^> 3w e Z*. A =4>* w.
(=4>) Indukcí k / dokážeme A e A/, =4> 3w e Z*. A =4>* w.
Základní krok / = 0: Platí triviálně, protože N0 = 0. Indukční krok: (IP) Tvrzení platí pro /. Dokážeme pro / + 1.
■ A g Nj. Tvrzení plyne z (IP).
■ A g A//+1 \ Nj. Pak existuje A^    .. .Xk e P,
kde každé Xy je terminál nebo neterminál patřící do A/,. Podle (IP) existuje wj tak, že Xj =4>* wj. Tedy A =4> X1 ... Xk =4>*    X2 ... Xk =4>* ... =4>* ^ ... í/i/^, kde    ... i/fy g Z*.
IB102 Automaty a gramatiky, 29.10.2018
12/18
Indukcí k n dokážeme
A 4> w, w g Z* =^ A e Nj pro nějaké /.
Základní krok n = 1: /I^i^gP okamžitě dává / = 1.
Indukční krok: (IP) Předpokládejme, že tvrzení platí pro všechna rí < n.
Nechť A n41 w. Pak A    X: ... Xk 4 w, kde Xy 4 i/i/y a ny < n.
Pokud Xj g A/, pak podle (IP) Xy g A/^ pro nějaké /).
Pokud Xj g Z, klademe /) = 0.
Položme / = 1 + maxj/i,..., ik}. Pak zřejmě A e A/,.
IB102 Automaty a gramatiky, 29.10.2018
13/18
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. Nechť g = (A/, Z, P, S) je CFG taková, že /_(£) ^ 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' = (A/e, Z, P;, S), kde
p = P n A/e x (A/e u Z)*. □
IB102 Automaty a gramatiky, 29.10.2018
14/18
Nalezení nepoužitelných symbolů typu II (neexistují a, (3 e (N ul.)* : S ^* aX(3)
Vstup:   CFG g = (A/, Z, P, S)
Výstup: CFG q' = (/V', Z', P', S) bez nedosažitelných symbolů splňující L{g) = L(g')
1: /:=0; V0 := {S}
2: repeat
3:      /:=/ + 1
4:      ty := ty_-, u {X g N u Z | 3/\ g ty_-, . /\ ->• a'X/3' g P} 5: until ty = ty_-|
6: N' := Nf] ty; I':=In ty; P' := P d (V, x ty*)
Korektnost: X g A/' u Z'        3a, /3 g (A/' u Z')*. S «X/5
IB102 Automaty a gramatiky, 29.10.2018
15/18
Příklad
q = ({S, A, B}, {a, b, c, d, e}, P, S), kde P obsahuje pravidla
S ->• aSb | c | aB A d A | d B eB
IB102 Automaty a gramatiky, 29.10.2018
16/18
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. Nechť 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 £-| odstraníme symboly typu II (výsledek označme q2). Platí L(S) = L(0i) = /.(&)■
IB102 Automaty a gramatiky, 29.10.2018 17/18
Korektnost: Dokážeme, že Q2 je redukovaná CFG.
Nechť X je libovolný symbol z Q2.
■ v Q2 existuje derivace S =4>^2 aXf3
■ všechny symboly z Q2 jsou též v
■ pro nějaký terminálni řetěz w platí S =4>^2 aXf3 w
■ žádný symbol z derivace aXfí      1/1/ není krokem 2 eliminován a proto aXf3 ^>*g2 w
Víme tedy, že existuje derivace S aX/3 =4>^2 1/1/, kde w\e termináln řetěz. Tudíž X není nepoužitelný v Q2.
IB102 Automaty a gramatiky, 29.10.2018