Greibachové normální forma
Definice 3.33. Bezkontextová gramatika G = (N, , P, S) je
v Greibachové normální formě (GNF) právě když
* G je bez -pravidel a
* každé pravidlo z P je tvaru A  a, kde a   a   N
(s případnou vyjímkou pravidla S  ).
Věta 3.34. Každý bezkontextový jazyk lze generovat bezkontextovou
gramatikou v Greibachové normální formě.
IB102 Automaty a gramatiky, 10. 11. 2008 1
Motivační příklad
A  BB | aAa | b
B  bBa | bAb
IB102 Automaty a gramatiky, 10. 11. 2008 2
Lemma o substituci (pro připomenutí)
Lemma 3.20. (o substituci)
Nechť G = (N, , P, S) je CFG. Nechť A  1B2  P.
Nechť B  1 | . . . | r jsou všechna pravidla v P tvaru B  .
Definujme G
= (N, , P
, S), kde
P
= (P {A  1B2})  {A  112 | . . . | 1r2}.
Pak L(G) = L(G
).
IB102 Automaty a gramatiky, 10. 11. 2008 3
Rekursivní neterminály a gramatiky
Definice 3.28. Neterminál A v CFG G = (N, , P, S) se nazývá
levorekursivní jestliže v G existuje derivace A +
A.
CFG bez levorekursivních neterminálů se nazývá nelevorekursivní.
Převod bezkontextové gramatiky G do GNF:
L(G) je prázdný: zřejmé (S  aS)
L(G) je neprázdný: 1. z vlastní gramatiky eliminujeme levou rekurzi
2. pak převedeme do GNF
IB102 Automaty a gramatiky, 10. 11. 2008 4
Algoritmus odstranění přímé levé rekurze
Nechť G = (N, , P, S) je bezkontextová gramatika, v níž všechna
A-pravidla (pravidla mající na levé straně A) jsou tvaru
A  A1 | . . . | Am | 1 | . . . | n,
kde každý řetěz i začíná symbolem různým od A.
Nechť G
= (N  {A
}, , P
, S), kde P
obdržíme z P tak, že všechna
výše uvedená pravidla nahradíme pravidly
A  1 | . . . | n | 1A
| . . . | nA
A
 1 | . . . | m | 1A
| . . . | mA
Pak L(G) = L(G
).
IB102 Automaty a gramatiky, 10. 11. 2008 5
Příklad
A  Bd | c
B  Bdd | Ccc | aAd
C  Aa
IB102 Automaty a gramatiky, 10. 11. 2008 6
Algoritmus odstranění levé rekurze
Vstup: Vlastní CFG G = (N, , P, S)
Výstup: Ekvivalentní nelevorekursivní gramatika
1 Uspořádej libovolně N, N = {A1, . . . , An}
2 for i  1 to n do
3 for j  1 to i - 1 do
4 foreach pravidlo tvaru Ai  Aj do
5 přidej pravidla Ai  1 | . . . | k
6 (kde Aj  1 | . . . | k jsou všechna Aj-pravidla)
7 vypusť pravidlo Ai  Aj od
8 od
9 odstraň případnou přímou levou rekurzi na Ai
10 od
IB102 Automaty a gramatiky, 10. 11. 2008 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é Ai-pravidlo buď
terminálem nebo neterminálem Ak, kde k > i.
2. po j-té iteraci vnitřního cyklu začíná každé Ai-pravidlo buď
terminálem nebo neterminálem Ak, kde k > j.
IB102 Automaty a gramatiky, 10. 11. 2008 8
Příklad
A  Ba | Db | c
B  CC
C  aE
D  CDa | Eb
E  bb
IB102 Automaty a gramatiky, 10. 11. 2008 9
Algoritmus transformace do GNF
Vstup: Nelevorekursivní CFG G = (N, , P, S) bez -pravidel
Výstup: CFG G
v GNF splňující L(G) = L(G
)
1 najdi lineární uspořádání  splňující (A  B)  P = A  B
2 Označme N = {A1, . . . , An | Ai-1  Ai, 1 < i  n}
3 for i  n - 1 downto 1 do
4 foreach pravidlo tvaru Ai  Aj, kde j > i
5 přidej pravidlo Ai  1 | . . . | k
6 (kde Aj  1 | . . . | k jsou všechna Aj-pravidla)
7 vypusť pravidlo Ai  Aj
8 od
9 od
10 nahraď potřebné terminály novými neterminály
11 a přidej příslušná pravidla
IB102 Automaty a gramatiky, 10. 11. 2008 10
Korektnost algoritmu
Konečnost.
Ekvivalence gramatik.
Výsledná gramatika je v GNF.
IB102 Automaty a gramatiky, 10. 11. 2008 11
Zásobníkové automaty
IB102 Automaty a gramatiky, 10. 11. 2008 12
Definice zásobníkového automatu
Definice 3.36. Nedeterministický zásobníkový automat (PushDown
Automaton, PDA) je sedmice M = (Q, , , , q0, Z0, F), kde
* Q je konečná množina, jejíž prvky nazýváme stavy,
*  je konečná množina, tzv. vstupní abeceda,
*  je konečná množina, tzv. zásobníková abeceda,
*  : Q × (  {}) ×   PF in(Q × 
), tzv. (parciální) přechodová
funkce1
,
* q0  Q je počáteční stav,
* Z0   je počáteční symbol v zásobníku,
* F  Q je množina koncových stavů.
1
Zápis PF in(Q × 
) značí množinu všech konečných podmnožin množiny Q × 
.
IB102 Automaty a gramatiky, 10. 11. 2008 13
Výpočet zásobníkového automatu
Definice 3.37. Nechť M = (Q, , , , q0, Z0, F) je PDA.
Konfigurací nazveme libovolný prvek (p, w, )  Q × 
× 
.
Na množině všech konfigurací automatu M definujeme binární relaci
krok výpočtu | M takto:
(p, aw, Z) | M (q, w, )
def
 (q, )  (p, a, Z) pro a    {}
Reflexivní a tranzitivní uzávěr relace | M značíme | 
M .
Je-li M zřejmý z kontextu, píšeme pouze | resp. | 
.
IB102 Automaty a gramatiky, 10. 11. 2008 14
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) = {w  
| (q0, w, Z0) | 
(qf, , ), kde qf  F,   
}
a jazyk akceptovaný PDA M prázdným zásobníkem definujeme
Le(M) = {w  
| (q0, w, Z0) | 
(q, , ), kde q  Q}.
IB102 Automaty a gramatiky, 10. 11. 2008 15