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 G iV* (s případnou výjimkou pravidla S —> e).
Věta 3.34. Každý bez kontextový jazyk lze generovat bezkontextovou gramatikou v Greibachové normální formě.
IB102 Automaty a gramatiky, 14.11.2011
1
Motivační příklad
A B
BB bBa
aAa bAb
IB102 Automaty a gramatiky, 14.11.2011
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 Q1 = (N, E, P', 5), kde
P' = (P \ {A     a1Ba2\) U {A ai/3ia2
aißra2}
PakL(0) = L(0')-
IB102 Automaty a gramatiky, 14.11.2011
3
Rekursivní neterminály a gramatiky
Definice 3.28. Neterminál A v CFG Q — (iV, £, P, 5) se nazývá levorekursivní jestliže v Q existuje derivace A =^>+ A/3.
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, 14.11.2011
4
Algoritmus odstranění přímé levé rekurze
Necht Q = (iV, S, P, S) je bezkontextová gramatika bez jednoduchých a ^-pravidel, v níž všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru
A -> Aai
Aam j3i
kde každý řetěz fy začína symbolem různým od A.
Necht g'=(NU {A'}, E, P', S), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly
A'
a
m
aiÄ
amA'
Pak L(g) = L(g').
IB102 Automaty a gramatiky, 14.11.2011
5
Příklad
A B
C
Bd
Bdd
Aa
c
Ccc aAd
IB102 Automaty a gramatiky, 14.11.2011
6
Algoritmus odstranění levé rekurze
Vstup: Vlastní CFG g = (iV, E, P, 5)
Výstup: Ekvivalentní nelevorekursivní gramatika
1 Uspořádej libovolně iV, N = {Ai,..., An}
2 for i <— 1 to n do for j     1 to i — 1 do
foreach pravidlo tvaru A{ přidej pravidla Ai —> fiia
3
4
5
6
7
8
AjOt do
(kde Aj -> fa výpust pravidlo A,
(3 k jsou všechna A^-pravidla)
Aja
od
g od
io odstraň případnou přímou levou rekurzi na A,t u od
IB102 Automaty a gramatiky, 14.11.2011
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 A^, 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.
IB102 Automaty a gramatiky, 14.11.2011
8
Příklad
A B C D E
Ba
CC
aE
CDa
bb
Db
c
Eb
IB102 Automaty a gramatiky, 14.11.2011
9
Algoritmus transformace do GNF
Vstup: Nelevorekursivní CFG Q = (iV, S, P, S) bez ^-pravidel Výstup: CFG Q' v GNF splňující L {Q) = L(0')
1 najdi lineární uspořádání -< splňující {A —t 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 | ... | fta
rj (kde Aj —> fii | ... | fik 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, 14.11.2011
10
Korektnost algoritmu
Konečnost. Ekvivalence gramatik. Výsledná gramatika je v GNF.
IB102 Automaty a gramatiky, 14.11.2011
11
Zásobníkové automaty
IB102 Automaty a gramatiky, 14.11.2011
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,
• Zq g T je počáteční symbol v zásobníku,
• F C Q je množina koncových stavů.
1Zá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, 14.11. 2011 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, 14.11.2011
14
Akceptující výpočet zásobníkového automatu
Definice 3.37.(pokračování)
Jazyk akceptovaný PDA Ai koncovým stavem definujeme jako
L(M) = {w G E* I (q0, w, Z0)       (qf, e, a), kde qf G F, a G T*}
a jazyk akceptovaný PDA Ai prázdným zásobníkem definujeme
Le(M) = {w G S* I (q0,w,Z0) kde g G Q}.
IB102 Automaty a gramatiky, 14.11.2011
15