Bezkontextové jazyky
Bezkontextová gramatika (context-free gram mar, CFG) q je čtveřice (A/,Z,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 T. = 0 (značení: V = Nu Z),
■ S g N je počáteční neterminál,
■ P c N x V* je konečná množina pravidel.
Jazyk je bezkontextový, pokud je generovaný nějakou bezkontextovou gramatikou.
IB102 Automaty, gramatiky a složitost, 13.10.2014
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, 13.10.2014
2/28
Derivační stromy pro bezkontextové gramatiky
Definice 3.1. Nechť G = {N, Z, P, S) je CFG.
Strom T nazveme derivačním stromem v q právě když
□ kořen má návěští S, vnitřní uzly mají návěští z N, listy mají návěští
z A/u Z u {e},
Q má-li vnitřní uzel návěští A a jeho všichni synové n^,...,nk
mají v uspořádání zleva doprava návěští X-\,... ,Xk e N uTu {e}, pak A    Xi... Xk g P,
Q 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, 13.10.2014
3/28
Vztah mezi derivačními stromy a relací ^*
Věta 3.3. Nechť g = {N, Z, P, S) je CFG. Pak pro libovolné a e (A/u Z)* platí S =4>* a právě když v £ existuje derivační strom s výsledkem a.
def
Důkaz. Označme q a = (A/, Z, P,A), kde A& N. Dokážeme, že pro každé A e N platí
/4     a <;=>-   v qa 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, 13.10.2014
4/28
Indukční krok k > 1:
(IP) Tvrzení platí pro stromy s nejvýše k -Strom T s k uzly:
1 vnitřními uzly.
je-li X; list, označme a-, = X, ■ není-li X, list, pak a, je výsledkem podstromu 7", s kořenem X, m výsledek T je a-i... an
Platí:   Xj     a-,   (pro X-„ které není listem, podle (IP))
A    X^ ... Xn 6 P (z definice derivačního stromu)
Dostáváme /A    X-i ... Xn     a-\ ... an.
IB102 Automaty, gramatiky a složitost, 13.10.2014
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 =4>* a.
Základní krok A => 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 k^ a, k > 0:
(IP) Pro každé B e N platí: pokud B^*/3v nejvýše k krocích, pak v qb existuje derivační strom s výsledkem /3.
«1... an, kde Xj =4> oĺj
Konstrukce stromu s výsledkem a:
IB102 Automaty, gramatiky a složitost, 13.10.2014
□
6/28
Jednoznačnost derivačních stromů
Derivace je sekvence S    a-i    a2    ... an-
Levá (resp. pravá) derivace je taková derivace, kde každé 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, 13.10.2014
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, 13.10.2014
8/28
Kanonické tvary bezkontextových gramatik
■ redukované bezkontextové gramatiky
■ gramatiky bez e-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, 13.10.2014
9/28
Redukované bezkontextové gramatiky
Definice 3.7. Symbol X e N u Z je nepoužitelný v CFG q = (N, Z,
právě když v q neexistuje derivace tvaru
S     wXy wxy
pro žádné w,x,y e Z*. Řekneme, že q je redukovaná, jestliže neobsahuje žádné nepoužitelné symboly.
X je nepoužitelý typu I (tj. nenormovaný)
X je nepoužitelý typu II (tj. nedosažitelný)
neexistuje iveľ splňující X =4>* w
neexistují a, (3 e (N u Z)* splňující S aX/3
IB102 Automaty, gramatiky a složitost, 13.10.2014
Nalezení nepoužitelných symbolů typu I (neexistuje w e Z*: A ^* w)
Vstup:   CFG q = (N, Z, P, S)
Výstup: Ne = {A \ 3w e Z*. A =4>* w} (normované neterminály) 1: / := 0; N0 := 0 2: repeat
3:      / := / + 1
4:      Nj :=        U{/l|/l^aeP, a G U Z)*}
5: until Ni = A/( !
6: A/e := Ni
IB102 Automaty, gramatiky a složitost, 13.10.2014
11/28
Korektnost algoritmu
Konečnost.
Správnost výsledku: Dokážeme A g Ne <s=^ 3w g Z*. A w.
(=^) Indukcí k / dokážeme A g A/( =>- 3w eT.*. A^* 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 N,. Tvrzení plyne z (IP).
■ A g A//+-, \ A/,. Pak existuje A^ X: ...Xk e P,
kde každé Xj je terminál nebo neterminál patřící do A/,. Podle (IP) existuje Wj tak, že Xj wy. Tedy A    X-\ ... Xk     w-\X2 ... Xk     ...     w-\ ... wk, kde Wi ... wk g T.*.
IB102 Automaty, gramatiky a složitost, 13.10.2014
12/28
(<í=) Indukcí k n dokážeme
A 4- w, w g T.* =>- A g N, pro nějaké /.
Základní krok n = 1: /1->ivéP 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 =>    ... Xk A w, kde Xj % wj a rij < n.
Pokud Xj g N, 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 g A/,-.
IB102 Automaty, gramatiky a složitost, 13.10.2014
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 0 Ne. □
Věta. Nechť G = (A/, Z, P, S) je CFG taková, že L(G) ^ 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' = (Ne, Z, P', S), kde
P' = p n Ne x (Ne u Z)*. □
IB102 Automaty, gramatiky a složitost, 13.10.2014
14/28
Nalezení nepoužitelných symbolů typu II (neexistují a,/5e(A/uI)*:S ^* aX(5)
Vstup:   CFG q = (N, Z, P, S)
Výstup: CFG G' = (N', T.', P', S) bez nedosažitelných symbolů splňující L{q) = L{q')
1: /:=0; V0 := {S} 2: repeat
3:      / := / + 1
4:      Vj :=       U {X e A/ U E | 34 e       . 4 a'X/3' g P}
5: until V( =
6: N' :=Nn V,; V := Z n 1//; P := Pil (V/ x V?)
Korektnost: XeWul'       3a, /3 g (A/' u Z')*. S ^* aXp
IB102 Automaty, gramatiky a složitost, 13.10.2014
15/28
Příklad
G = {{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, 13.10.2014
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 G-\). Krok 2. Z Q-\ odstraníme symboly typu II (výsledek označme Q2). Platí L(G) = L(G,) = L(G2).
IB102 Automaty, gramatiky a složitost, 13.10.2014 17/28
Korektnost: Dokážeme, že Q2 je redukovaná CFG.
Nechť X je libovolný symbol z Q2.
m v Q2 existuje derivace S aX/3
■ všechny symboly z Q2 jsou též v
m pro nějaký terminálni řetěz w platí S      aX(3 w
■ žádný symbol z derivace aX/3      w není krokem 2 eliminován a proto       =>g2 w
Víme tedy, že existuje derivace S =^2 aXfi =^2 w, kde wje terminálni řetěz. Tudíž X není nepoužitelný v g2. □
IB102 Automaty, gramatiky a složitost, 13.10.2014
18/28
-pravidla
Definice 3.13. Řekneme, že CFG G = (N, Z, P, S) je bez e-pravidel
právě když buď
Q P neobsahuje žádné e-pravidlo (tj. pravidlo tvaru A    e) nebo
0 v P existuje právě jedno e-pravidlo S    e a S se nevyskytuje na pravé straně žádného pravidla z P.
IB102 Automaty, gramatiky a složitost, 13.10.2014
19/28
Příklad
G = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S aAbBc
A      BB | a | e B ^ AcA \ b
IB102 Automaty, gramatiky a složitost, 13.10.2014
20/28
Algoritmus pro odstranění -pravidel
Vstup:   CFG Q = {N, Z, P, S)
Výstup: CFG G' = (N', Z, P, S') bez e-pravidel splňující L(G) =
1: Zkonstruuj Ne = {A g N \ A ^* e} 2: Množinu pravidel P' zkonstruuj takto: 3: for all A ->•    ... Xn g P do
4:     přidej do P' všechna pravidla tvaru      a-\ ...an splňující
5: (a) pokud Xj £ N£ pak a-, = 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 N£ then
10:     přidej do P' pravidla S'    S | e 11: N':=NU{S'} 12: else
13:      A/' := N; S' := S 14: end if
IB102 Automaty, gramatiky a složitost, 13.10.2014
Příklad
G = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S     aAbBc | AB A      BB | a | e B     AA I b
IB102 Automaty, gramatiky a složitost, 13.10.2014
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez -pravidel. Ekvivalence gramatik.
IB102 Automaty, gramatiky a složitost, 13.10.2014
23/28
Jednoduchá pravidla
Jednoduchým pravidlem nazýváme každé pravidlo tvaru A A, B e N.
S -+ aAbBc
A      aA | B | a
B     bB I b
IB102 Automaty, gramatiky a složitost, 13.10.2014
Algoritmus pro odstranění jednoduchých pravidel
Vstup:   CFG Q = (A/, Z, P, S) bez e-pravidel Výstup: CFG Q' = (N, Z, P', S) bez jednoduchých a e-pravidel, kde L(G) = L{q')
1: for all /A g N do
2:      / := 0; N0 := {A} 3: repeat
4: /:=/ + 1
5: A/,- := A//_i U {C | fl     C e P, Be A/,_i}
6:     until A/( = A//_-| 7:      NA := A/( 8: end for
9: P' := 0
10: for all A g A/ do
11:     P' ■= P' u {A    a | S g A/4 A S    a g P není jednoduché} 12: end for
IB102 Automaty, gramatiky a složitost, 13.10.2014
25/28
Příklad
G = ({S, A, B, C}, {a, b, c}, P, S), kde P obsahuje pravidla
S ABC
A aA | B | a
B bB | A
C cC I A
IB102 Automaty, gramatiky a složitost, 13.10.2014
26/28
Korektnost algoritmu
Konečnost.
Výsledná gramatika neobsahuje jednoduchá pravidla ani -pravidla. Ekvivalence gramatik:
L(Q') Q L(Q) Nechť w e L(g'), pak existuje derivace
S = OtQ =>gi «1 =4>g' . . . =>gi OLn = W.
Pokud bylo při kroku a-, =>gi použito pravidlo A ->•(3, pak existuje nějaké B e Na takové, že v Q platí A     Ba B ->•/3. Tedy v £ platí
/4      /3 a a,- .
c L(G') Nechť w g /.(<?), pak existuje levá derivace
S = a0 =4>g a-i =4>g . . . =4>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, 13.10.2014
27/28
Vlastní bezkontextová gramatika
Definice 3.17. CFG Q = (N, 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 symbolu, bez e-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 e-pravidla a jednoduchá pravidla. Odstraněním nepoužitelných symbolu pak získáme vlastní gramatiku. □
IB102 Automaty, gramatiky a složitost, 13.10.2014
28/28