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, gramatiky a složitost, 2.11.2015
1/22
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 -> £C, kde B.CeN 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, gramatiky a složitost, 2.11.2015
Příklad
Q = ({S, A, B}, {a, b}, P, S), kde P obsahuje pravidla
S ->• AS | a A     AB | AA
B ->• b
IB102 Automaty, gramatiky a složitost, 2.11.2015
3/22
Algoritmus transformace do CNF
L = 0
Gramatiku pro L převedeme na vlastní a bez jednoduchých pravidel.
X ->• e X ->• a X >A X aĎ X ->• ae X -> Afc> X ^ AB
X -> aScD
IB102 Automaty, gramatiky a složitost, 2.11.2015
4/22
Lemma o vkládání pro bezkontextové jazyky
Věta 3.24. Nechť L je CFL. Pak existují p,qgN (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, gramatiky a složitost, 2.11.2015
5/22
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Nechť Z. 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, gramatiky a složitost, 2.11.2015
6/22
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 Z. 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 T a v něm (libovolnou) nejdelší cestu C.
IB102 Automaty, gramatiky a složitost, 2.11.2015
7/22
Na cestě C lze zvolit tři uzly 1/1, u2l u3 s vlastnostmi:
□ uzly 1/1, L/2 jsou označeny týmž neterminálem, řekněme A B    leží blíže ke kořenu než u2
B L/3 je list
□ cesta z 1/1 do u3 má délku nejvýše k
IB102 Automaty, gramatiky a složitost, 2.11.2015
8/22
IB102 Automaty, gramatiky a složitost, 2.11.2015 9/22
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 Z. 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 zgí. delší než n takové, že
pro všechny slova u, v, w, x, y splňující z = uvwxy, vx ^ e a |iwx| < n
existuje / g N0 takové, že uv'wx'y ^ L
IB102 Automaty, gramatiky a složitost, 2.11.2015 10/22
Příklad použití Lemmatu o vkládání
L = {äti d | / > 1}
Pro libovolnou konstantu n eN
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 g L
L není CFL.
IB102 Automaty, gramatiky a složitost, 2.11.2015
11/22
Rekursivní neterminály a gramatiky
Definice 3.28. Neterminál A v CFG Q = (A/, Z, P, S) se nazývá levorekursivní jestliže v Q existuje derivace A =4>+ Af3.
CFG bez levorekursivních neterminálů se nazývá nelevorekursivní.
Je-li v CFG pravidlo tvaru A -> Aa, hovoříme o přímé levé rekursi na A.
Praktický význam: některé nástroje pro automatickou tvorbu parserů k zadaným gramatikám vyžadují na vstupu nelevorekursivní gramatiku (např. ANTLR).
IB102 Automaty, gramatiky a složitost, 2.11.2015
12/22
Algoritmus odstraněni prime leve rekurze
Nechť CFG Q = (A/, Z, P, S) je necyklická a bez ^-pravidel, v níž všechna /A-pravidla (pravidla mající na levé straně A) jsou tvaru
A    Aol\   ...  Aam /3i
kde každý retez /3, začíná symbolem různým od A.
Nechť = (Nu {A'}, Z, P', S), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly:
Ä ->■
Ai I Ä A'
am ol\AI
PnAf amÄ
Pak L(Q) = /_(£') a Q' je necyklická a bez ^-pravidel.
IB102 Automaty, gramatiky a složitost, 2.11.2015
13/22
Lemma o substituci
Lemma 3.20. (o substituci)
Nechť g = {N, E, P, S) je CFG. Nechť A^a, Ba2 e P. Nechť B ->• /?i | ... | /3r jsou všechna pravidla v P tvaru S -> o.
Definujme £' = (A/, E, P', S), kde
P' = (P \ {/A    «iBa2}) u {/A ->■ OL\ß^a2
a-\ßra2}
Pak L(£) = /.(£')■
IB102 Automaty, gramatiky a složitost, 2.11.2015
14/22
A ->• Bd B Bdd C ^ Aa
Ccc aAd
IB102 Automaty, gramatiky a složitost, 2.11.2015
Algoritmus odstranění levé rekurze
Vstup:   Vlastní CFG Q = (A/, Z, P, S)
Výstup: Ekvivalentní nelevorekursivní gramatika bez ^-pravidel
Uspořádej libovolně N, N = {A|,..., An} for / <- 1 to n do
for y <- 1 to / - 1 do
for all pravidlo tvaru A, -> Aja do přidej pravidla A-, ^ faa \ ... \ fS^a (kde Aj ^ fa \ ... \ f3k jsou všechna pravidla pro Aj) vypusť pravidlo A, Aja end for end for
odstraň případnou přímou levou rekursi na A, end for
IB102 Automaty, gramatiky a složitost, 2.11.2015
16/22
Korektnost algoritmu
Konečnost.
Ekvivalence gramatik: Všechny úpravy jsou dle Lemmatu o substituci nebo odstraňují přímou levou rekursi.
Výsledná gramatika je nelevorekursivní:
D po Mé iteraci vnějšího cyklu začíná každé A-pravidlo buď terminálem nebo neterminálem Ak, kde k > i.
h po /-té iteraci vnitřního cyklu začíná každé A-pravidlo buď terminálem nebo neterminálem Ak, kde k > j.
Výsledná gramatika je bez ^-pravidel.
IB102 Automaty, gramatiky a složitost, 2.11.2015
17/22
Greibachové normální forma
Definice 3.33. Bezkontextová gramatika Q = (A/, Z, P, S) je v Greibachové normální formě (GNF), právě když
■ Q je bez ^-pravidel a
■ každé pravidlo z P je tvaru A    aa, kde a g Z a a g A/* (s případnou výjimkou pravidla S e).
Věta 3.34. Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Greibachové normální formě.
IB102 Automaty, gramatiky a složitost, 2.11.2015
18/22
Zásobníkové automaty
IB102 Automaty, gramatiky a složitost, 2.11.2015
19/22
Definice zásobníkového automatu
Definice 3.36. Nedeterministický zásobníkový automat (PushDown Automaton, PDA) je sedmice M = (Q, 51, r, S, q0, Z0, F), kde
■ Q je konečná množina, jejíž prvky nazýváme stavy,
■ Z je konečná množina, tzv. vstupní abeceda,
■ ľ je konečná množina, tzv. zásobníková abeceda,
■ S : Q x (Z u {s}) xľ4 VFin{0 x r*), tzv. (parciální) přechodová funkce1,
■ Qo e Q je počáteční stav,
■ Zq g r je počáteční symbol v zásobníku,
■ F c Q je množina koncových stavů.
1 Zápis Vr,n{Q x T*) značí množinu všech konečných podmnožin množiny Q x r*.
IB102 Automaty, gramatiky a složitost, 2.11.2015 20/22
Výpočet zásobníkového automatu
Definice 3.37. Nechť M = (Q, Z, r, 6, gb, Z0, F) je PDA.
Konfigurací nazveme libovolný prvek (p, w, a) e Q x Z* x r*.
Na množině všech konfigurací automatu M definujeme binární relaci krok výpočtu takto:
(p,aw,Za) ^ (q,w,-ya) ^ 3(q,-y) e 5(p,a,Z) pro aeluje}
Reflexivní a tranzitivní uzávěr relace hn- značíme
M ----| ^ ■
V     ■  _ _   ' l^-i-      ■ _ ' V  _   _ _   _      _   _ _       I ____ I*
Je-li .M zrejmý z kontextu, píšeme pouze |— resp.
IB102 Automaty, gramatiky a složitost, 2.11.2015 21/22
Akceptující výpočet zásobníkového automatu
Definice 3.37. (pokračování)
Jazyk akceptovaný PDA M koncovým stavem definujeme jako
L(M) = {weZ*\ (<7o, w, Z0) ^- (qf, e,a), kde qf e F, a e P} a jazyk akceptovaný PDA M prázdným zásobníkem definujeme jako
Le(M) = {w e Z* | (q0, w, Z0) ^- (q, s, s), kde qeQ}.
IB102 Automaty, gramatiky a složitost, 2.11.2015
22/22