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 A/n Z = 0 (značení: V = Nu Z),
■ S g N je počáteční neterminál,
■ P c A/ x y* je konečná množina pravidel.
Jazyk je bezkontextový, pokud je generovaný nějakou bezkontextovou gramatikou.
IB102 Automaty, gramatiky a složitost, 26.10.2015
1/28
Příklad
G = {{E, T, F}, {+, *, (,), /'}, P, E), kde P obsahuje pravidla
E ^ E+T \ T T      T* F | F F -+ (E) | /
IB102 Automaty, gramatiky a složitost, 26.10.2015
2/28
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 >4    X| ... X/, 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, gramatiky a složitost, 26.10.2015
3/28
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, gramatiky a složitost, 26.10.2015
4/28
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 7} s kořenem X,
■ výsledek 7 je
Platí:   Xj =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>*
IB102 Automaty, gramatiky a složitost, 26.10.2015
5/28
{=^) Nechť A =4>* 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 =4>* f3 v nejvýše k krocích, pak v QB existuje derivační strom s výsledkem f3.
A      a    =4>    A ^ Xi ... Xn 4> «1 ...     kde X\ a\
Konstrukce stromu s výsledkem a\
IB102 Automaty, gramatiky a složitost, 26.10.2015
□
6/28
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, gramatiky a složitost, 26.10.2015
7/28
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, gramatiky a složitost, 26.10.2015
8/28
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, gramatiky a složitost, 26.10.2015
9/28
Redukované bezkontextové gramatiky
Definice 3.7. Symbol X e N u Z je nepoužitelný v CFG q = (A/, Z, P, S) právě když v £ 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^gF (tj. nenormovaný) splňující X =4>* w
X je nepoužitelný typu II <=^> neexistují a,/3 e (NuZ) (tj. nedosažitelný) splňující S =4>*
IB102 Automaty, gramatiky a složitost, 26.10.2015
10/28
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; N0 := 0
2: repeat
3:      / := /' + 1
4:      A// := /v",_-| U{/A|/A^oeP, a e (A//_i U Z)*}
5: until A/,- = A/,_i
6: A/e := A/,
IB102 Automaty, gramatiky a složitost, 26.10.2015 11/28
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      X^ ...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>*    .. .wk, kde 1/1/1 ... W/k £ 51*.
IB102 Automaty, gramatiky a složitost, 26.10.2015
12/28
(<==) Indukcí k n dokážeme
A A w, w g Z* =4> A g A/, pro nějaké /.
Základní krok n = 1: /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    XA ... Xk 4 w, kde Xy 4 wj 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 + max{/-|,..., ik}. Pak zřejmě A g A/,.
IB102 Automaty, gramatiky a složitost, 26.10.2015
13/28
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, P7, S), kde
P = P n A/e x (A/e U Z)*. □
IB102 Automaty, gramatiky a složitost, 26.10.2015
14/28
Nalezení nepoužitelných symbolů typu II (neexistují a,(3 e (A/uZ)* : S^* aX(3)
Vstup:   CFG Q = (A/, I, P, S)
Výstup: CFG Q' = (A/', Z', P', S) bez nedosažitelných symbolů splňující L(G) = L(Q')
1: /:=0; V0 := {S}
2: repeat
3:      / := /' + 1
4:      ty :=       U {X e A/ U Z | 3/A e V-^.A^ a'X(3' e P} 5: until ty = ty_i
6: N' := A/n ty; I' :=In V); P' := Pfl (ty x ty*)
Korektnost: X e N' uT.' ^ 3a, /3 e (A/' u Z')*. S ^* aX/3
IB102 Automaty, gramatiky a složitost, 26.10.2015
15/28
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, gramatiky a složitost, 26.10.2015
16/28
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ť Z. 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 G2). Platí L{G) = L&) = L{g2).
IB102 Automaty, gramatiky a složitost, 26.10.2015 17/28
Korektnost: Dokážeme, že Q2 je redukovaná CFG.
Nechť X je libovolný symbol z Q2.
■ v Q2 existuje derivace S =4>^2
■ 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 w není krokem 2 eliminován a proto aXf3 ^>*g2 w
Víme tedy, že existuje derivace S =4>^2 w, kde w\e termináln
řetěz. Tudíž X není nepoužitelný v Q2.
IB102 Automaty, gramatiky a složitost, 26.10.2015
-pravidla
Definice 3.13. Řekneme, že CFG Q = (A/, Z, P, S) je bez -pravidel
právě když buď
D P neobsahuje žádné ^-pravidlo (tj. pravidlo tvaru A    e) nebo
H v P existuje právě jedno ^-pravidlo S    e a S se nevyskytuje na pravé straně žádného pravidla z P.
IB102 Automaty, gramatiky a složitost, 26.10.2015
19/28
Příklad
q = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S ->• aAbBc A BB B     AcA I b
e
IB102 Automaty, gramatiky a složitost, 26.10.2015
20/28
Algoritmus pro odstranění -pravidel
Vstup:   CFG q = (A/, Z, P, S)
Výstup: CFG £7 = (A/7, Z, P7, S7) bez ^-pravidel splňující /_(£) = L{$')
1: Zkonstruuj A/e = {A e N \ A e} 2: Množinu pravidel P7 zkonstruuj takto: 3: foralM-^Xf ...Xn e P do
4:     přidej do P7 všechna pravidla tvaru A       ... an splňující
5: (a) pokud Xj £ N£ pak a j = X,
6: (b) pokud Xj g N£ pak a\ je buď X, nebo e
7: (c) ne všechna a\ jsou £
8: end for
9: if S g A/£ then
10:     přidej do P' pravidla S7    S \ e
11:      A/7 := A/U{S7}
12: else
13:      A/7 := A/; S7 := S
14: end if
IB102 Automaty, gramatiky a složitost, 26.10.2015
21/28
Příklad
q = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S ->• aAbBc | AB A ->■ BB | a | e B ^ AA \ b
IB102 Automaty, gramatiky a složitost, 26.10.2015
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez -pravidel. Ekvivalence gramatik.
IB102 Automaty, gramatiky a složitost, 26.10.2015
23/28
Jednoduchá pravidla
Jednoduchým pravidlem nazýváme každé pravidlo tvaru A ->• B, kde A B e N.
S ->• aAbBc A ^ aA \ B B ^ bB I b
IB102 Automaty, gramatiky a složitost, 26.10.2015
24/28
Algoritmus pro odstranění jednoduchých pravidel
Vstup:   CFG g = (A/, Z, P, S) bez s-pravidel
Výstup: CFG q' = (A/, Z, P', S) bez jednoduchých a e-pravidel, kde
L(g) = L(g>)
for all A e N do
/ := 0; Nq := {A}
repeat
/ := / + 1
Ni := A/,_1 U{C|6^CgP, BgA/m} until A/, = A/,-_i
A(a == A//
end for
P' :=0
for all >4 e A/ do
p' := p' u {A    a |   e A(a a   ->> a e P není jednoduché} end for
IB102 Automaty, gramatiky a složitost, 26.10.2015
25/28
Příklad
g = ({S, A, B, C}, {a, b, c}, P, S), kde P obsahuje pravidla
/A ->■ a/A | S
e    Ďfí | /i
C ^ cC \ A
IB102 Automaty, gramatiky a složitost, 26.10.2015
Korektnost algoritmu
Konečnost.
Výsledná gramatika neobsahuje jednoduchá pravidla ani -pravidla. Ekvivalence gramatik:
L(Q') c L(G) Nechť w e L(gf), pak existuje derivace
Pokud bylo při kroku a-, ^g> použito pravidlo A /3, pak existuje nějaké B e NA takové, že v Q platí A =4>* B a B    f3. Tedy v Q platí
A =4>* f3 a a/ =4>* .
L(G) c /-(£') Nechť w e /.(£), pak existuje levá derivace
Tu lze rozdělit na úseky tak, že v celém úseku se použila pouze jednoduchá pravidla anebo žádné jednoduché pravidlo. Úseky s jednoduchými pravidly lze nahradit.
IB102 Automaty, gramatiky a složitost, 26.10.2015
27/28
Vlastní bezkontextová gramatika
Definice 3.17. CFG Q = (A/, Z, P, S) se nazývá necyklická, právě když neexistuje A e N takový, že A =4>+ A.
Q se nazývá vlastní, právě když je bez nepoužitelných symbolů, bez ^-pravidel a necyklická.
Věta 3.18. Ke každému neprázdnému bezkontextovému jazyku existuje vlastní bezkontextová gramatika, která jej generuje.
Důkaz. Z bezkontextové gramatiky pro neprázdný jazyk odstraníme ^-pravidla a jednoduchá pravidla. Odstraněním nepoužitelných symbolů pak získáme vlastní gramatiku. □
IB102 Automaty, gramatiky a složitost, 26.10.2015
28/28