Greibachové normální forma
Definice 3.33. Bezkontextová gramatika Q — (iV,       S) je
v Greibachové normální formě (GNF) právě když
• Q je bez e-pravidel a
• každé pravidlo z P je tvaru A —> aa, kde a £ S a a £ iV* (s případnou výjimkou pravidla 5 —č).
Věta 3.34. Každý bezkontextový jazyk lze generovat bez kontextovo u gramatikou v Greibachové normální formě.
IB102 Automaty a gramatiky, 12.11.2012
1
Motivační příklad
A B
BB bBa
aAa bAb
IB102 Automaty a gramatiky, 12.11.2012
2
Lemma o substituci (pro připomenutí)
Lemma 3.20.   (o substituci)
Necht g = (N, E, P, S) je CFG. Necht A -> aľBa2 G P. Necht B —> fii I ... I (3r jsou všechna pravidla v P tvaru B
a,
Definujme Q' = (iV, E, P', 5), kde
P' = (P \ {A     aľBa2}) U {A^ axß\Qi2
aißra2}
PakL(£) = L(g').
IB102 Automaty a gramatiky, 12.11.2012
3
Rekursivní neterminály a gramatiky
Definice 3.28. Neterminál A v CFG Q — (iV, 5) se nazývá levorekursivní jestliže v C/ existuje derivace A =^>+ A/5.
CFG bez levorekursivních neterminálů se nazývá nelevorekursivní.
Převod bezkontextové gramatiky Q do GNF:
L(Q) je prázdný:    zřejmé (S —> aS)
L{Q) je neprázdný: 1. z vlastní gramatiky eliminujeme levou rekurzi
2. pak převedeme do GNF
IB102 Automaty a gramatiky, 12.11.2012
4
Algoritmus odstranění přímé levé rekurze
Necht CFG Q = (iV, S) je necyklická a bez e-pravidel, v níž všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru
A -> Aai
Aam fii
kde každý řetěz    začíná symbolem různým od A.
Necht Q' — (N U {A1}, E, P', 5), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly
A'
a
m
aľAf
amAř
Pak L (Q) = L(Q') a C/'je necyklická a bez ^-pravidel
IB102 Automaty a gramatiky, 12.11.2012
5
Příklad
A B
C
Bd
Bdd
Aa
c
Ccc aAd
IB102 Automaty a gramatiky, 12.11.2012
6
Algoritmus odstranění levé rekurze
Vstup: Vlastní CFG g = (iV, E, P, 5)
Výstup: Ekvivalentní nelevorekursivní gramatika bez e-pravidel
1 Uspořádej libovolně iV, N = {Ai,..., An}
2 for i <— 1 to n do for j <— 1 to i — 1 do
3
4
5
6
8
foreach pravidlo tvaru Ai —> Aja do
přidej pravidla Ai —> fiia
fiká
(kde Aj -> fa výpust pravidlo A%
fik jsou všechna A^-pravidla)
AjCt
od
g od
io odstraň případnou přímou levou rekurzi na Ai u od
IB102 Automaty a gramatiky, 12.11.2012
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-té  iteraci vnějšího cyklu  začíná  každé A^-pravidlo bud terminálem nebo neterminálem Ak, kde k > i.
2. po j-té iteraci vnitřního cyklu začíná  každé A^-pravidlo bud terminálem nebo neterminálem A^, kde k > j.
Výsledná gramatika je bez e-pravidel.
IB102 Automaty a gramatiky, 12.11.2012
8
Příklad
A B C D E
Ba CC aE CDa bb
Db
c
Eb
IB102 Automaty a gramatiky, 12.11.2012
9
Algoritmus transformace do GNF
Vstup: Nelevorekursivní CFG Q = (iV, S, P, S) bez ^-pravidel Výstup: Ekvivalentní gramatika v GNF
1 najdi lineární uspořádání -< splňující (A —> Ba) £ P        A B
2 Označme N = {Ai,..., An \ Ai-i -< A^ 1 < i < n}
3 for i <— n — 1 downto 1 do
4 foreach pravidlo tvaru Ai —> AjOt, kde j > i do
5 přidej pravidlo Ai —> /3ia | ... | /J^a
e (kde Aj —> fii | ... | fy jsou všechna A^-pravidla)
7        výpust pravidlo Ai —> AjOt s od g od
io náhrad potřebné terminály novými neterminály u a přidej příslušná pravidla
IB102 Automaty a gramatiky, 12.11.2012
10
Korektnost algoritmu
Konečnost. Ekvivalence gramatik. Výsledná gramatika je v GNF.
IB102 Automaty a gramatiky, 12.11.2012
11
Zásobníkové automaty
IB102 Automaty a gramatiky, 12.11.2012
12
Definice zásobníkového automatu
Definice 3.36. Nedeterministický zásobníkový automat (PushDown
Automatem, PDA) je sedmice M = (Q, S, r, 5, qo, Z$, F), kde
• Q je konečná množina, jejíž prvky nazýváme stavy,
• S je konečná množina, tzv. vstupní abeceda,
• T je konečná množina, tzv. zásobníková abeceda,
• 5 : Q x (S U {e}) xT^ Vfíu(Q x T*), tzv. (parciální) přechodová funkce1,
• Qo £ Q Je počáteční stav,
• Z0 g r je počáteční symbol v zásobníku,
• F C Q je množina koncových stavů.
^ápis Vfíu(Q x T*) značí množinu všech konečných podmnožin množiny Q x r*.
IB102 Automaty a gramatiky, 12.11. 2012 13
Výpočet zásobníkového automatu
Definice 3.37.    Necht M = (Q, £, I\ 5, q0, Z0, F) je PDA. Konfigurací nazveme libovolný prvek (p,w,a) £ Q x S* x T*
Na množině všech konfigurací automatu      definujeme binární relaci
krok výpočtu
m
takto:
(p, <m>, Za)
(g, i/;, 7a) 3(#, 7) G 5(p, a, Z) pro a G S U {e}
Reflexivní a tranzitivní uzávěr relace
m
značíme
Je-li Ai zřejmý z kontextu, píšeme pouze I— resp
m
*
IB102 Automaty a gramatiky, 12.11.2012
14
Akceptující výpočet zásobníkového automatu
Definice 3.37.(pokračování)
Jazyk akceptovaný PDA J\A koncovým stavem definujeme jako
L(M) = {w £ S* I (q0, w, Z0) P- (g/, e, a), kde qf £ F,a £ T*}
a jazyk akceptovaný PDA      prázdným zásobníkem definujeme
Le(M) =     e £* | (qr0, w, Z0) P- (g, e, e), kde g G Q}.
IB102 Automaty a gramatiky, 12.11.2012
15