Příklad
M = ({q0,p, /}, {a, b}, {A, B, Z}, S, q0, Z, {/}), kde
o
6(q0,a,Z) a, A)
a, B)
b, Z) b,A) b,B) e,Z) e,A) e,B)
5(p, a, A) 6(p, b, B) S(p,e,Z)
S(q
S(qo
%o %o S(qo
S(qo
S(q
o
{(9o {(9o {(9o {(9o
{(</ {(9o
= UQO
AZ)} A A)} AB)} BZ)}
BA) }
BB) }
{(P,B)}
{(P,e)} {(f,Z)}
IB102 Automaty a gramatiky, 21.11. 2011
1
Příklad
M = ({q0}, {a, b}, {Z, A}, S, q0, Z, 0), kde
S(q0,a,Z) = {(qo,A)} S(q0,a,A) = {(q0,AA)} 6(q0,b,A) = {(q0,e)}
IB102 Automaty a gramatiky, 21.11. 2011
2
Ekvivalence dvou způsobů akceptování
Věta 3.39.   Pro každý jazyk L platí:
L = L (AT) pro nějaký PDA M        L = Le(M) pro nějaký PDA M.
Důkaz,  koncový stav =^> prázdný zásobník
Intuice:
K danému AT zkonstruujeme Ai simulující jeho činnost.
Vejde-li Af do koncového stavu, Ai se nedeterministicky rozhodne
• pokračovat v simulaci automatu AT nebo
• přejít do nově přidaného stavu q£l v němž vyprázdní zásobník.
IB102 Automaty a gramatiky, 21.11. 2011
3
Komplikace
Řešení: před zahájením simulace bude u Ai na dně zásobníku nový symbol, který nedovolíme odstranit jinde, než ve stavu q£.
IB102 Automaty a gramatiky, 21.11. 2011
4
Konstrukce: Necht N = (Q, S, T, S, q0, Z0, F).
Klademe M = (Q U {q'0,qe} , S, T U {Z'} , 5', q'0, Z', 0), kde Z' ^ r, gó?9e ^ Q a 5' je definována takto:
. S'(q>0}s}Z') = {(qo,Z0Z')}
• jestliže 5{q,a,Z) obsahuje (r,7), pak Sf(q:a:Z) obsahuje (r,7)
• S'(q,e,Z) obsahuje (q£,Z)
pro všechny geFaZeTU {Z'}
• S'(qe,e,Z) = {(qe,e)} pro všechny Z G T U {Z'}
IB102 Automaty a gramatiky, 21.11. 2011
5
Korektnost:
IB102 Automaty a gramatiky, 21.11. 2011
6
prázdný zásobník =^> koncový stav
Intuice
K danému Ai zkonstruujeme M simulující jeho činnost.
• AT si před simulací přidá na dno zásobníku nový symbol.
• Je-li Aí schopen číst tento symbol (tj. zásobník automatu M je prázdný) tak AT přejde do nově přidaného stavu qf, který je koncovým stavem.
IB102 Automaty a gramatiky, 21.11. 2011
7
Konstrukce: Necht M = (Q,E,r,S,q0,Z0,^).
Klademe N = (Q U {q'0} qf} , S , V U {Z'} , S', q'0, Z', {qf}), kde Z7 ^ T,     Qf Č Q a ^ Je definována takto:
• jestliže 5(q,a,Z) obsahuje (r,7), pak 8'(q,a,Z) obsahuje (r,7)
. <5'(g, e, Z') = {(«/, e)}
pro všechny q <E Q □
IB102 Automaty a gramatiky, 21.11. 2011
8
Grafická reprezentace konfigurací
IB102 Automaty a gramatiky, 21.11. 2011
9
Rozšírený zásobníkový automat
Definice 3.44.       Rozšírený zásobníkový automat je sedmice
K=(Q,'Ľ,r,6,q(hZo,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 x (S U {e}) x T* do konečných podmnožin množiny Q x r*.
Pojmy konfigurace a akceptovaný jazyk (koncovým stavem, prázdným
^- definujeme
zásobníkem) zůstávají beze změny.   Krok výpočtu
takto:
(q, w,j2oí) 4=> =1(2,72) G 5(p,a,7i) pro a £ SU{e}
(p, <m>, 71a)
IB102 Automaty a gramatiky, 21.11. 2011
10
Příklad
= ({Qo,P, f}, {a, b, c, d}, {A, B, Z}, 5, q0, Z, {/}), kde
6(q0,a,e) = {(q0,A)}
S(q0,b,e) ={(q0,B)}
6(q0,e,e) = {(p,e)}
S(p,a,A) = {(p,e)}
6(p,b,B) ={(p,e)}
6(p,c,AA) ={(p,e)} 5(p,c,BBB)= {(p,e)}
S(p,d}Z) ={(/,£)}
IB102 Automaty a gramatiky, 21.11. 2011
11
Ekvivalence rozšířených PDA a PDA
Lemma 3.45. Ke každému rozšírenému PDA existuje ekvivalentní (obyčejný) PDA.
Intuice:
IB102 Automaty a gramatiky, 21.11. 2011 12
Důkaz. Necht U = (Q, S, I\ 6, q0, Z0, F) je rozšířený PDA a
ra = max{|o;| | %,a,a) je definováno pro nějaké qeQ,ae EU{e}}
Definujeme V = (Qi, S,Ti, Si,Qi, ZuFi)> kde
•Qi = {[q,a\ I 9 € Q, a e rj, 0 < |a| < m},
• Ti = T U {Zi}, kde Z\ je nový symbol,
• Qi = [qo, Z0Z™ ],
• Fi = {[q,a] \ q e F,a eTl, 0 < \a\ < m}.
IB102 Automaty a gramatiky, 21.11. 2011
13
5± je definována takto:
jestliže 5(q, a, X\... Xk) obsahuje (r, Yi... Yi), pak l > k
5i([q, X\... XkOí], a, Z) obsahuje ([r,/3],7Z), kde f3y = Y\... YJa a     = m, pro všechny Z G I\ a a G     takové, že
— rn —
k
l < k
5i([q, X\... XkQt], a, Z) obsahuje ([r, Yí... Y\aZ\,s) pro všechny Z G Ti a a G r* takové, že |a| = m — k
8i{[q,ai\,e,Z) = {([g,aZ],e)}
pro všechny q G Q, Z G I\ a a G r* takové, že \a\ < m
IB102 Automaty a gramatiky, 21.11. 2011
14
Korektnost:  Ověříme, že platí
(g, aw, X\... XkXk+i... Xn)
^> ([g, a], au;, /3) ^-(
r, a
^(r,w, Yi
• YiXk+i • • • Xn)
kde:
1.      — X\... -X^iv]71,
2. a//^ — Yi... Y/Xfc+i... XnZf\
a'
= m a
4. mezi dvěma výše uvedenými konfiguracemi PDA V neexistuje taková konfigurace, kde druhá komponenta stavu (tj. buffer) by měla délku m.
□
IB102 Automaty a gramatiky, 21.11. 2011
15