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, 30.10.2017
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, 30.10.2017
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, 30.10.2017
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, 30.10.2017
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, 30.10.2017
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 f3 v nejvýše k krocích, pak v QB existuje derivační strom s výsledkem f3.
A      a    =4>    A =4> Xi ... Xn 4> a<\ ... an, kde X\ ^> a/
Konstrukce stromu s výsledkem a:
IB102 Automaty a gramatiky, 30.10.2017
□
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, 30.10.2017
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, 30.10.2017
8/18
Kanonické tvary bezkontextových gramatik
■ redukované bezkontextové gramatiky
■ gramatiky bez ^-pravidel
■ gramatiky bez jednoduchých pravidel
■ Chomského normálni forma
■ gramatiky bez levé rekurze
■ Greibachové normální forma
IB102 Automaty a gramatiky, 30.10.2017
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, 30.10.2017
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, 30.10.2017 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 Nj =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, 30.10.2017
12/18
Indukcí k n dokážeme
A 4 w, w g Z* =>► A g Nj pro nějaké /.
Základní krok n = 1: /I-ii^gP okamžitě dává / = 1.
Indukční krok: (IP) Předpokládejme, že tvrzení platí pro všechna rí < n.
Nechť A n41 iv. Pak A    X| ... X/, 4 iv, kde Xy 4 i/i/y a ny < n.
Pokud Xy g A/, pak podle (IP) Xy g A/^ pro nějaké /).
Pokud Xy g Z, klademe /) = 0.
Položme / = 1 + maxj/i,..., //<}. Pak zřejmě A e A//.
IB102 Automaty a gramatiky, 30.10.2017
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, 30.10.2017
14/18
Nalezení nepoužitelných symbolů typu II (neexistují a, (3 e {N u Z)* : S ^* aXp)
Vstup:   CFG G = (A/, Z, P, S)
Výstup: CFG Q' = (A/', Z'7 P', S) bez nedosažitelných symbolů splňující L(g) = L(g')
1: /:=0; V0 := {S}
2: repeat
3:      /:=/ + 1
4:      V- := Vi-i U{X £ NuZ\3Ae       ./A ->■ a'X£' G P} 5: until V/ =
6: N' := Nil V,; I':=In \//; P':=Píl(V, x V,*)
Korektnost: XeA/'uľ       3a, /? e (A/' u Z')*. S ^* aXp
IB102 Automaty a gramatiky, 30.10.2017
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, 30.10.2017
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, 30.10.2017 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 aX/3      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, 30.10.2017