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, 24.10.2016
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 -> 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, gramatiky a složitost, 24.10.2016
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, 24.10.2016
3/22
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, gramatiky a složitost, 24.10.2016
4/22
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, gramatiky a složitost, 24.10.2016
5/22
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, gramatiky a složitost, 24.10.2016
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 /.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, gramatiky a složitost, 24.10.2016
7/22
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, gramatiky a složitost, 24.10.2016
8/22
IB102 Automaty, gramatiky a složitost, 24.10.2016 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 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, gramatiky a složitost, 24.10.2016 10/22
Příklad použití Lemmatu o vkládání
L = {áb'c' | / > 1}
Pro libovolnou konstantu n eN
existuje slovo z e L delší než n takové, že
pro všechny slova l/, v, w, x, y splňující z = uvwxy, vx ^ e a vwx < n
existuje / g N0 takové, že uv'wx'y 0 L
=^> L není CFL.
IB102 Automaty, gramatiky a složitost, 24.10.2016
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, 24.10.2016
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ť = (N (J {A'}, Z, P', S), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly:
A' ->■
I Ä A'
am ol\AI
PnA'
amÄ
Pak L(Q) = /_(£') a Q' je necyklická a bez ^-pravidel.
IB102 Automaty, gramatiky a složitost, 24.10.2016
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 /_(£) = /.(£')■
IB102 Automaty, gramatiky a složitost, 24.10.2016
14/22
A ->• Bd B Bdd C ^ Aa
Ccc aAd
IB102 Automaty, gramatiky a složitost, 24.10.2016
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 / <- 1 to / - 1 do
for all pravidlo tvaru A, -> Aja do přidej pravidla Ai -> 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, 24.10.2016
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.
b 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, 24.10.2016
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, 24.10.2016
18/22
Zásobníkové automaty
IB102 Automaty, gramatiky a složitost, 24.10.2016
19/22
Definice zásobníkového automatu
Definice 3.36. Nedeterministický zásobníkový automat (PushDown Automaton, PDA) je sedmice M = (Q, Z, l~, 5, 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,
■ r je konečná množina, tzv. zásobníková abeceda,
■ S : Q x (Z u {e}) xľ^ VfíhÍO x P), 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 Vfíh{Q x r*) značí množinu všech konečných podmnožin množiny Q x r*.
IB102 Automaty, gramatiky a složitost, 24.10.2016 20/22
Výpočet zásobníkového automatu
Definice 3.37. Nechť M = (Q, Z, r, 6, q0, 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, 24.10.2016 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*\ (qo, w, Zq) ^- (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* | (qo, w, Z0) ^- (q, s, e), kde q e Q}.
IB102 Automaty, gramatiky a složitost, 24.10.2016
22/22