Greibachové normální forma
Definice 3.33. Bezkontextová gramatika Q = {N, Y,, P, S) je
v Greibachove normálni forme (GNF) práve kdyZ
• Q je bez ^-pravidel a
• kaZde pravidlo z P je tvaru A — oa, kde o G Y a a G N * (s případnou vyjímkou pravidla S — e).
Veta 3.34. KaZdy bezkontextovy jazyk lze generovat bezkontextovou gramatikou v Greibachove normalní forme.
IB102 Automaty a gramatiky, 15.11.2010
1
Motivační příklad
A — BB j aAa j h B — hBa \ hAh
IB102 Automaty a gramatiky, 1S. 11. 2010
2
Lemma o substituci (pro připomenutí)
Lemma 3.20.   (o substituci)
Necht G = (N, S, P, S) je CFG. Necht A — axBa2 G P. Necht B —/?i | ... | /3r jsou všechna pravidla v P tvaru B — a.
Definujme G' = (N, S, P', S), kde
P' = (P \ {A — a1Ba2}) U {A — a1p1a2 | ... | a1 (3ra2}.
Pak L(G) = L(G7).
IB102 Automaty a gramatiky, 15. 11. 2010
3
Rékursivn í nétérminály a gramatiky
Définicé 3.28. Neterminal A v CFG G = (N, S, P, S) se nazyva lévorékursivní jestliZe v G existuje derivace A =^>+ A/3.
CFG bez levorekursivních neterminaiu se nazyva nélévorékursivn í.
Prévod bézkontéxtové gramatiky G do GNF:
L(G) je prázdny:    zrejme (S —» aS)
L(G) je neprázdny: 1. z vlastní gramatiky eliminujeme levou rekurzi
2. pak převedeme do GNF
IB102 Automaty a gramatiky, 15. 11. 2010
4
Algoritmus odstranění přímé levé rekurze
Necht G = (N, S, P, S) je bezkontextova gramatika bez jednoduchých a ^-pravidel, v níZ všechna A-pravidla (pravidla mající na leve strane A) jsou tvaru
A — Aai | ... | Aam | /?i | ... | /3n, kde kaZdý retez & zacína symbolem rUzným od A.
Necht G7 = (N U {A7}, S, P', S), kde P' obdrzíme z P tak, ze všechna výše uvedena pravidla nahradíme pravidlý
A — & | ... | pn | či A' | ... | ^nA'
A' — ai | ... | am | aiA' | ... | amA'
Pak L(G) = L(G').
IB102 Automatý a gramatiký, 15.11.2010
5
Příklad
A - Bd j c
B -   Bdd j Ccc j aAd
C - Aa
IB102 Automaty a gramatiky, 1S. 11. 2010
6
Algoritmus odstranění levé rekurze
Vstup: Vlastní CFG G = (N, S, P, S)
Výstup: Ekvivalentní nelevorekursivní gramatika
1 Usporadej libovolne N, N = {Al,..., An}
2 for i — 1 to n do
3 for j — 1 to i — 1 do
4 foreach pravidlo tvaru Ai —» Aj a do
5 pridej pravidla Ai — pla | ... | ^ka
6 (kde Aj — ^l | ... | flk jsou všechna Aj-pravidla)
7 vypust pravidlo Ai — Aj a od
8 od
9 odstraň prípadnou prímou levou rekurzi na Ai
10 od
IB102 Automaty a gramatiky, 15.11.2010
7
Korektnost algoritmu
Konečnost.
Ekvivalence gramatik: Všechny úpravy jsou dle Lemmatu o substituci nebo odstraňují přímou levou rekurzi.
Výsledná gramatika je nelevorekursivní:
1. po i-te iteraci vnejsího cyklu  zaCína  kaZde A^-pravidlo bucJ terminalem nebo neterminalem Ak, kde k > i.
2. po j-te iteraci vnitrního cyklu zacína  kaZde A^-pravidlo bucJ terminalem nebo neterminalem Ak, kde k > j.
IB102 Automaty a gramatiky, 15.11.2010
8
A — Ba | Db | c
B — CC
C — aE
D — CDa | Eb
E — bb
Příklad
IB102 Automaty a gramatiky, 15.11.2010
9
Algoritmus transformace do GNF
Vstup: Nelevorekursivní CFG G = (N, S, P, S) bez ^-pravidel Výstup: CFG G' v GNF splňující L(G) = L(G')
1 najdi linearn í uspoňadan í -<< splňuj íc í (A — Ba) G P =>* A -<< B
2 Oznacme N = {A1,..., An | Ai-1 -<     1 < i < n}
3 for i — n — 1 downto 1 do
4 foreach pravidlo tvaru Ai — Aj a, kde j > i
5 pridej pravidlo Ai —       | ... | /3ka
6 (kde Aj — ^1 | ... | /3k jsou vsechna Aj-pravidla)
7 vypust pravidlo Ai — Aj a
8 od
9 od
10 nahracJ potňebne terminaly novymi neterminaly
11 a pňidej pňíslusna pravidla
IB102 Automaty a gramatiky, 15.11.2010
10
Korektnost algoritmu
Konečnost. Ekvivalence gramatik. Výsledná gramatika je v GNF.
IB102 Automaty a gramatiky, 15.11.2010
11
Zásobníkové automaty
IB102 Automaty a gramatiky, 15.11.2010
12
Definice zasobn íkoveiio automatu
Definice 3.36. Nedeterministický zasobn íkový automat (PushDown
Automaton, PDA) je sedmice M = (Q, S, r, ô, q0, Z0, F), kde
• Q je koneCna množina, jejíž prvky nazývame stavý,
• S je koneCna množina, tzv. vstupn í abeceda,
• r je koneCna množina, tzv. zasobn íkova abeceda,
• ô : Q x (S U {e}) x r —> VFin(Q x r*), tzv. (parcialní) prechodova funkce1,
• qo £ Q je pocatecn í stav,
• Z0 G r je pocatecn í sýmbol v zasobn íku,
• F C Q je mnozina koncových stavu.
1Zapis PFin(Q x r*) znaCí mnozinu vsech konecných podmnozin mnoziny Q x r*.
IB102 Automaty a gramatiky, 15. 11. 2010
13
Výpočet zásobníkového automatu
Definice 3.37.    Necht M = (Q, S, r, ô, q0, Z0, F) je PDA. Konfigurací nazveme libovolný prvek (p,w,a) G Q x S* x r*.
Na mnoZine vsech konfigurací automatu M definujeme binární relaci krok výpočtu takto:
(p, aw, Za) (g, w, ja) 3(g, 7) G 5(p, a, Z) pro a G S U {č}
Reflexivní a tranzitivní uzávěr relace
značíme
*
M
M
Je-li Ai zřejmý z kontextu, píšeme pouze |— resp.
*
IB102 Automaty a gramatiky, 15.11.2010
14
Akceptuj íc i výpoCet zásobn íkoveiio automatu
Definice 3.37.(pokraCovan í)
Jazýk akceptovaný PDA M koncovým stavem definujeme jako
L(M) = {w G S* I (g0, w, Z0) P~ (qf, e, a), kde qf e F,a e T*} a jazyk akceptovany PDA M prazdným zasobn íkem definujeme
Le(M) =     G £* | (g0,w,Z0) p- kde g G Q}.
IB102 Automaty a gramatiky, 15.11. 2010 15