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, 4.11.2019
1/18
Příklad
G = {{E, T, F}, {+, *, (,), /'}, P, E), kde P obsahuje pravidla
E -+ E+ T | T T -+ T* F | F F -+ (E) | /
IB102 Automaty a gramatiky, 4.11.2019
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 {e}, 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, 4.11.2019
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, 4.11.2019
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 X, list, označme a; = X,
■ není-li X, list, pak a-, je výsledkem podstromu T, s kořenem X,
■ výsledek T je a1 ...
Platí:   X, =4>* a,-   (pro X,, které není listem, podle (IP))
A    X1 ... Xn g P (z definice derivačního stromu)
Dostáváme /A ^> X1 ... Xn =4>* a1 ... an.
IB102 Automaty a gramatiky, 4.11.2019
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 =>* j3 v nejvýše k krocích, pak v qb existuje derivační strom s výsledkem f3.
A      a    =4>    A=> X-\ ... Xn A> ol-\ ... an, kde X\ ^ ol\
Konstrukce stromu s výsledkem a\
IB102 Automaty a gramatiky, 4.11.2019
□
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, 4.11.2019
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, 4.11.2019
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, 4.11.2019
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, 4.11.2019
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, 4.11.2019 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é Xj 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/i^ ... i/i^, kde 1/1/1 ... i/fy g Z*.
IB102 Automaty a gramatiky, 4.11.2019
12/18
(<==) Indukcí k n dokážeme
A 4> i/i/, w g Z* =4> >A g A/, 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.PaWA^    ...XkA w, kde Xj 4 wj a ny < n.
Pokud Xy g A/, pak podle (IP) Xj g    pro nějaké /}.
Pokud Xj g Z, klademe /ý = 0.
Položme / = 1 + max{/i,..., //c}. Pak zřejmě A g A/,.
IB102 Automaty a gramatiky, 4.11.2019
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, 4.11.2019
14/18
Nalezení nepoužitelných symbolů typu II (neexistují a, (3 e (N ul.)* : S ^* aX(3)
Vstup:   CFG g = (N, E, P, S)
Výstup: CFG Q' = (A/', E', P', S) bez nedosažitelných symbolů splňující L(Q) = L(g')
1: /:=0; V0 := {S}
2: repeat
3:      /:=/ + 1
4:       ty := ty_-, u {X g N u E | 34 g ty_-, . 4 ->• a'X/3' g P} 5: until V/ = ty_i
6: N' := Nf] ty; E' := E n ty; P':=Pn( ty x ty*)
Korektnost: XeN'uľ        3a, /3 g (A/' u E')*. S ^* aX0
IB102 Automaty a gramatiky, 4.11.2019
15/18
Příklad
q = ({S, A, B}, {a, b, c, d, e}, P, S), kde P obsahuje pravidla
S     aSb | c A ->• d A | d B ->■ eS
IB102 Automaty a gramatiky, 4.11.2019
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, 4.11.2019 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, 4.11.2019