Příklad
M = ({q0, p, f}, {a, b}, {A, B, Z}, , q0, Z, {f}), kde
(q0, a, Z) = {(q0, AZ)}
(q0, b, Z) = {(q0, BZ)}
(q0, a, A) = {(q0, AA)}
(q0, b, A) = {(q0, BA)}
(q0, a, B) = {(q0, AB)}
(q0, b, B) = {(q0, BB)}
(q0, , Z) = {(p, Z)}
(q0, , A) = {(p, A)}
(q0, , B) = {(p, B)}
(p, a, A) = {(p, )}
(p, b, B) = {(p, )}
(p, , Z) = {(f, Z)}
IB102 Automaty a gramatiky, 24. 11. 2008 1
Příklad
M = ({q0}, {a, b}, {Z, A}, , q0, Z, ), kde
(q0, a, Z) = {(q0, A)}
(q0, a, A) = {(q0, AA)}
(q0, b, A) = {(q0, )}
IB102 Automaty a gramatiky, 24. 11. 2008 2
Ekvivalence dvou způsobů akceptování
Věta 3.39. Pro každý jazyk L platí:
L = L(N) pro nějaký PDA N  L = Le(M) pro nějaký PDA M.
Důkaz. koncový stav = prázdný zásobník
Intuice:
K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
* pokračovat v simulaci automatu N nebo
* přejít do nově přidaného stavu q, v němž vyprázdní zásobník.
IB102 Automaty a gramatiky, 24. 11. 2008 3
Komplikace:
Řešení: před zahájením simulace bude u M na dně zásobníku nový
symbol, který nedovolíme odstranit jinde, než ve stavu q.
IB102 Automaty a gramatiky, 24. 11. 2008 4
Konstrukce: Nechť N = (Q, , , , q0, Z0, F).
Klademe M = (Q  {q
0, q} ,  ,   {Z
} , 
, q
0 , Z
, ),
kde Z
/ , q
0, q / Q a 
je definována takto:
* 
(q
0, , Z
) = {(q0, Z0Z
)}
* jestliže (q, a, Z) obsahuje (r, ), pak 
(q, a, Z) obsahuje (r, )
* 
(q, , Z) obsahuje (q, Z)
pro všechny q  F a Z    {Z
}
* 
(q, , Z) = {(q, )}
pro všechny Z    {Z
}
IB102 Automaty a gramatiky, 24. 11. 2008 5
Korektnost:
IB102 Automaty a gramatiky, 24. 11. 2008 6
prázdný zásobník = koncový stav
Intuice:
K danému M zkonstruujeme N simulující jeho činnost.
* N si před simulací přidá na dno zásobníku nový symbol.
* Je-li N schopen číst tento symbol (tj. zásobník automatu M je
prázdný) tak N přejde do nově přidaného stavu qf, který je koncovým
stavem.
IB102 Automaty a gramatiky, 24. 11. 2008 7
Konstrukce: Nechť M = (Q, , , , q0, Z0, ).
Klademe N = (Q  {q
0, qf} ,  ,   {Z
} , 
, q
0 , Z
, {qf}),
kde Z
/ , q
0, qf / Q a 
je definována takto:
* 
(q
0, , Z
) = {(q0, Z0Z
)}
* jestliže (q, a, Z) obsahuje (r, ), pak 
(q, a, Z) obsahuje (r, )
* 
(q, , Z
) = {(qf, )}
pro všechny q  Q 2
IB102 Automaty a gramatiky, 24. 11. 2008 8
Grafická reprezentace konfigurací
IB102 Automaty a gramatiky, 24. 11. 2008 9
Rozšířený zásobníkový automat
Definice 3.44. Rozšířený zásobníkový automat je sedmice
R = (Q, , , , q0, Z0, F), kde
* všechny symboly až na  mají tentýž význam jako v definici PDA,
*  je zobrazením
z konečné podmnožiny množiny Q × (  {}) × 
do konečných podmnožin množiny Q × 
.
Pojmy konfigurace a akceptovaný jazyk (koncovým stavem, prázdným
zásobníkem) zůstávají beze změny. Krok výpočtu | R definujeme
takto:
(p, aw, 1) | R (q, w, 2)
def
 (q, 2)  (p, a, 1) pro a  {}
IB102 Automaty a gramatiky, 24. 11. 2008 10
Příklad
R = ({q0, p, f}, {a, b, c, d}, {A, B, Z}, , q0, Z, {f}), kde
(q0, a, ) = {(q0, A)}
(q0, b, ) = {(q0, B)}
(q0, , ) = {(p, )}
(p, a, A) = {(p, )}
(p, b, B) = {(p, )}
(p, c, AA) = {(p, )}
(p, c, BBB) = {(p, )}
(p, d, Z) = {(f, )}
IB102 Automaty a gramatiky, 24. 11. 2008 11
Ekvivalence rozšířených PDA a PDA
Lemma 3.45. Ke každému rozšířenému PDA existuje ekvivalentní
(obyčejný) PDA.
Intuice:
IB102 Automaty a gramatiky, 24. 11. 2008 12
Důkaz. Nechť R = (Q, , , , q0, Z0, F) je rozšířený PDA a
m = max{|| | (q, a, ) je definováno pro nějaké q  Q, a    {}}.
Definujeme P = (Q1, , 1, 1, q1, Z1, F1), kde
* Q1 = {[q, ] | q  Q,   
1, 0  ||  m},
* 1 =   {Z1}, kde Z1 je nový symbol,
* q1 = [q0, Z0Zm-1
1 ],
* F1 = {[q, ] | q  F,   
1, 0  ||  m}.
IB102 Automaty a gramatiky, 24. 11. 2008 13
ˇ 1 je definována takto:
­ jestliže (q, a, X1 . . . Xk) obsahuje (r, Y1 . . . Yl), pak
l  k
1([q, X1 . . . Xk], a, Z) obsahuje ([r, ], Z),
kde  = Y1 . . . Yl a || = m,
pro všechny Z  1 a   
1 takové, že || = m - k
l < k
1([q, X1 . . . Xk], a, Z) obsahuje ([r, Y1 . . . YlZ], )
pro všechny Z  1 a   
1 takové, že || = m - k
­ 1([q, ], , Z) = {([q, Z], )}
pro všechny q  Q, Z  1 a   
1 takové, že || < m
IB102 Automaty a gramatiky, 24. 11. 2008 14
Korektnost: Ověříme, že platí
(q, aw, X1 . . . XkXk+1 . . . Xn) | R (r, w, Y1 . . . YlXk+1 . . . Xn)
 ([q, ], aw, ) | +
P ([r, 
], w, 
),
kde:
1.  = X1 . . . XnZm
1 ,
2. 

= Y1 . . . YlXk+1 . . . XnZm
1 ,
3. || = |
| = m a
4. mezi dvěma výše uvedenými konfiguracemi PDA P neexistuje taková
konfigurace, kde druhá komponenta stavu (tj. cache) by měla délku m.
2
IB102 Automaty a gramatiky, 24. 11. 2008 15