Příklad
M = ({q0,P, /}, {a, b}, {A, B, Z], S, q0, Z, {/}), kde
S(qo
S(q
S(q
a, Z) a, A)
a, B)
b, Z) b,A) b,B) e,Z) e,A) e,B)
o
= uqo
= {(« = {(90
{(</
{(Qo {(Qo {(<*
O
AZ)} A A)} AB)} BZ)}
BA) }
BB) }
5(p, a, A) <5(p, b, B) S(p,e,Z)
{(P,B)}
{(P,e)} {{f,Z)}
IB102 Automaty a gramatiky, 19.11.2012
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) = {(qo,e)}
IB102 Automaty a gramatiky, 19.11.2012
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, 19.11.2012
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, 19.11.2012
4
Konstrukce: Necht Af = (Q, E, I\ S, q0, Z0, F).
Klademe M = (QU {q'0, q£} , E , T U {Z'} , 5', q'0 , Z', 0), kde Z' ^ r, gó^e ^ Q a 5' je definována takto:
• S'(q'0,e,Z') = {(q0,Z0Z')}
• jestliže 5(q,a,Z) obsahuje (r,7), pak 8'{q,a,Z) obsahuje (r,7)
• S'(q,£,Z) obsahuje (qs,Z)
pro všechny geFaZeTU {Z'}
• S'(qe,e,Z) = {(qe,e)} pro všechny Z e T U {Z'}
IB102 Automaty a gramatiky, 19.11.2012
5
Korektnost:
IB102 Automaty a gramatiky, 19.11.2012
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 qj, který je koncovým stavem.
IB102 Automaty a gramatiky, 19.11.2012
7
Konstrukce: Necht M = (Q,T,,F,5,q0, Zo,0).
Klademe N = (Q U {q'0} qf} , S , T U {Z'} , 5', q'Q, Z', {qf}), kde Z7 ^ T,     9/ ^ Q a & Je definována takto:
• jestliže 5(q,a,Z) obsahuje (r,7), pak 5r(q,a,Z) obsahuje (r, 7) pro všechny q <E Q □
IB102 Automaty a gramatiky, 19.11.2012
8
Grafická reprezentace konfigurací
IB102 Automaty a gramatiky, 19.11.2012
9
Rozšírený zásobníkový automat
Definice 3.44.       Rozšírený zásobníkový automat je sedmice
K=(Q,'Ľ,r,6,qo,Zo,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:
w,72o0 4=^> 3(2,72) G 5(p,a,7i) pro a £ SU{e}
(p, <m>, 71a)
7£
IB102 Automaty a gramatiky, 19.11.2012
10
Příklad
= ({qo,P,f},{aibicid}ÁAiB,Z},5,q0,Z,{f}), kde
S(q0,a,e) = {(q0,A)}
6(q0,b,e) ={(q0,B)}
S(q0,e,e) = {(p,s)}
S(p,a,A) = {(p,s)}
S(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, 19.11.2012
11
Ekvivalence rozšířených PDA a PDA
Lemma 3.45. Ke každému rozšířenému PDA existuje ekvival (obyčejný) PDA.
Intuice:
IB102 Automaty a gramatiky, 19.11.2012
Důkaz. Necht 1Z = (Q, S, r, 5, q0, Z$, F) je rozšírený PDA a
m — max{|a| | S(q, a, a) je definováno pro nějaké q G Q, a G S U {e}}
Definujeme P = (Qi, S, Ti, 5l5 gl5 Zi,F{), kde
Qi = {[g, a] | q G Q, a G r*, 0 < |a| < m}, Ti = T U {Zi}f kde Z\ je nový symbol,
9i = [Qo, ZQZ™~1],
Fľ = {[q, a] | g e F, a e TJ, 0 < a < m}.
IB102 Automaty a gramatiky, 19.11.2012
13
Si je definována takto:
jestliže 5(q, a, X\... XjS) obsahuje (r, Yi... Y/), pak l > k
5i([q, Xi... Xfca], a, Z) obsahuje ([r, 7Z),
kde ^7 = Yi... Y\ol a |/3| = m,
pro všechny Z e Y\ a a e r* takové, že \a\ = m — k
l < k
5i([q, X\... X^a], a, Z) obsahuje ([r, Yi... Y\aZ\é) pro všechny Z £ Ti a a £ r* takové, že |a| = m —
bx{\q,a\s,Z) = {([qr,aZ],e)}
pro všechny g e Q, Z G Ti a a G T* takové, že \a\ < m
IB102 Automaty a gramatiky, 19.11.2012
14
Korektnost:  Ověříme, že platí
(g, aw, Xi... XkXk+i... Xn)
r, a
ir(r,w,Y1
• YiXk+i... Xn)
kde:
1. a(5 — X\... XnZYi,
2. a'/?' = Yi... YiXk+i • • • XnZf\
3.
= 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, 19.11.2012
15