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, 5.11.2018
1/21
-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 a gramatiky, 5.11.2018
2/21
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 a gramatiky, 5.11.2018
3/21
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 a gramatiky, 5.11.2018
4/21
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 a gramatiky, 5.11.2018
5/21
Korektnost algoritmu
Konečnost.
Výsledná gramatika je bez -pravidel. Ekvivalence gramatik.
IB102 Automaty a gramatiky, 5.11.2018
6/21
Jednoduchá pravidla
Jednoduchým pravidlem nazýváme každé pravidlo tvaru A ->• B, kde A B e N.
S ->• aAbBc A -> a/A | B B ^ bB \ b
IB102 Automaty a gramatiky, 5.11.2018
7/21
Algoritmus pro odstranění jednoduchých pravidel
Vstup:   CFG g = (N, Z, P, S) bez e-pravidel
Výstup: CFG Q' = (/V, Z, P', S) bez jednoduchých a e-pravidel, kde
L(Q) = L(gf)
for all A e N do
/ := 0; A/0 := {A}
repeat
/ := / + 1
Ni := A/,_1 u{C |       Cg P, BeN^} until A/, = A/,_1
A(4 == A//
end for
P' :=0
for all /A g A/ do
p' := p' u {A    a | e e NA a 6    a e P není jednoduché} end for
IB102 Automaty a gramatiky, 5.11.2018
8/21
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 a gramatiky, 5.11.2018
9/21
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>* S a B    f3. Tedy v Q platí
/A =4>* /j a a/ =4>* .
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 a gramatiky, 5.11.2018
10/21
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.
<? 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 a gramatiky, 5.11.2018
11/21
Chomského normální forma
Definice 3.19. Bezkontextová gramatika Q = (A/, Z, P, S) je
v Chomského normální formě (CNF), právě když Q je bez ^-pravidel
každé pravidlo z P má jeden z těchto tvarů:
D A -> BC, kde B,C e N E A^ř a, kde a g Z
Věta 3.21. Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Chomského normální formě.
IB102 Automaty a gramatiky, 5.11.2018
Příklad
Q = ({S, A, B}, {a, b}, P, S), kde P obsahuje pravidla
S ->• AS | a A     AB | AA
B ->• b
IB102 Automaty a gramatiky, 5.11.2018
13/21
Algoritmus transformace do CNF
L = 0
Gramatiku pro L převedeme na vlastní a bez jednoduchých pravidel.
X -7 E
X a X A X ab X aB X -+ Ab X ^ AB
X aBcD
IB102 Automaty a gramatiky, 5.11.2018
14/21
Lemma o vkládání pro bezkontextové jazyky
Věta 3.24. Nechť L je CFL. Pak existují p, q e N (závisející na Ľ) taková, že každé slovo z e L delší než p lze psát ve tvaru z = uvwxy, kde
■ alespoň jedno ze slov v, x je neprázdné (tj. vx ^ e),
■ |iwx| < q a
■ uv'wx'y g L pro každé / g N0.
Poznámka 3.25. Tvrzení zůstává v platnosti i když namísto konstant p, q budeme všude psát jen (jedinou) konstantu n.
IB102 Automaty a gramatiky, 5.11.2018
15/21
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Nechť /_je generován gramatikou v CNF.
délka cesty z kořene do listu
= počet modrých hran
= počet neterminálů na cestě -1
hloubka stromu
= maximální délka cesty
Derivační strom hloubky k má max. 2k listů =4> slovo délky nejvýše 2k. Derivační strom pro slovo delší než 2/c_1 má cestu délky alespoň k. Tato cesta obsahuje alespoň k + 1 neterminálů.
IB102 Automaty a gramatiky, 5.11.2018
16/21
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Nechť L je generován gramatikou Q = (A/, Z, P, S), která je v CNF. Označme /c = card(N) a položme p = 2/c_1, q = 2k.
Nechť z g /.je slovo delší než p. Pak v libovolném derivačním stromu slova z existuje cesta délky alespoň k. Zvolme pevně jeden takový strom Tav něm (libovolnou) nejdelší cestu C.
IB102 Automaty a gramatiky, 5.11.2018
17/21
Na cestě C lze zvolit tři uzly   , u2l u3 s vlastnostmi:
□ uzly , l/2 jsou označeny týmž neterminálem, řekněme A B    leží blíže ke kořenu než l/2
B l/3 je list
□ cesta z    do u3 má délku nejvýše k
IB102 Automaty a gramatiky, 5.11.2018
18/21
IB102 Automaty a gramatiky, 5.11.2018 19/21
Použití Lemmatu o vkládání pro bezkontextové jazyky
Lemma o vkládání je implikace P =4> Q, kde P je výrok, že L je CFL a Q jsou uvedené vlastnosti.
Obměnu Lemmatu o vkládání -nQ =4> -iP lze použít k důkazu, že nějaký jazyk L není CFL — stačí, když ukážeme platnost -nQ.
Q:
Pro libovolnou konstantu n e N
existuje slovo z e L delší než n takové, že
pro všechny slova u, v, w, x, y splňující z = uvwxy, vx ^ e a |vwx| < n
existuje / g N0 takové, že uv'wx'y ^ L
IB102 Automaty a gramatiky, 5.11.2018 20/21
Příklad použití Lemmatu o vkládání
L = {a'b'c' | / > 1}
Pro libovolnou konstantu n g N
existuje slovo z g L delší než n takové, že
pro všechny slova u, v, w, x, y splňující z = uvwxy, vx ^ e a vwx < n
existuje / g N0 takové, že uv'wx'y g L
=^> L není CFL.
IB102 Automaty a gramatiky, 5.11.2018
21/21