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, gramatiky a složitost, 26.10.2015
1/28
Příklad
G = {{E, T, F}, {+, *, (,), /'}, P, E), kde P obsahuje pravidla
£ ^ £+ľ | 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 >A    X| ... X/c g P,
B 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, 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 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, gramatiky a složitost, 26.10.2015
5/28
{=^) 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 =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 ... an, kde X, ol\ 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>* i/i/xy
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, f3 e (N u Z) (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; 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, 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 A^    .. .Xk e P,
kde každé Xy je terminál nebo neterminál patřící do A/,. Podle (IP) existuje wj tak, že Xy =4>* wj. Tedy A =4> X1 ... Xk =4>*    X2 ... Xk =4>* ... =4>* ^ ... í/i/^, kde    ... i/fy g Z*.
IB102 Automaty, gramatiky a složitost, 26.10.2015
12/28
(<==) 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 % w. Pak A       ... Xk 4 iv, kde Xj 4 i/i/y a rij < n.
Pokud Xy e A/, pak podle (IP) Xy e A/^ pro nějaké /).
Pokud Xj e 51, klademe /) = 0.
Položme / = 1 + max{/-|Jk}. Pak zřejmě A e 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, P;, 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 (NuZ)* : S^* aX/3)
Vstup:   CFG g = (A/, Z, P, S)
Výstup: CFG Q' = (N', Z', P', S) bez nedosažitelných symbolů splňující L(Q) = L(Q')
1: /:=0; V0 := {S}
2: repeat
3:      / := /' + 1
4:     l/,- := u {X e /Vu Z | EL4 e      .>A -> a'X/3' e P}
5: until V/ =
6: N' := N(~) V,; I' :=In V,-; P' := P n (V/ x V*)
Korektnost: X e A/' u Z' ^ 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ť 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{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 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, 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    £ 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    = (A/', Z, P', S') bez ^-pravidel splňující L{$) = L{$')
1: Zkonstruuj A/e = {A e N \ A e} 2: Množinu pravidel P' zkonstruuj takto: 3: foralM-^Xf ...Xn e P do
4:     přidej do P' 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 e
8: end for
9: if S g A/£ then
10:     přidej do Pf pravidla Sř    S | e
11:      A/' := A/U{S'}
12: else
13:      A/' := A/; S' := 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 q = (N, Z, P, S) bez e-pravidel
Výstup: CFG q' = (A/, Z, P', S) bez jednoduchých a e-pravidel, kde
for all A e N do
/ := 0; N0 := {A} repeat
/ := / + 1
Nj := A/,_1 u{C | B^ Cg P, BeNi-i} until A/, = A/,_1 Ah := A/,
end for
P' :=0
for all A g A/ do
p' := p1 u {/A    a | 6 g A//\ a B    a g P není jednoduché} end for
IB102 Automaty, gramatiky a složitost, 26.10.2015
25/28
Příklad
G = ({S, A, B, C}, {a, Ď, c}, P, S), kde P obsahuje pravidla
S 4BC
/A ->■ a/A | B B ĎB | 4 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{Qf) c L(Q) Nechť w e L(Q'), pak existuje derivace
Pokud bylo při kroku a-, =4>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í
L(G) c        Nechť i/i/ e L(<?), pak existuje levá derivace
S = a q =>g ol\ =4>g . . . =>g an = W.
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