Príklad
M = ({qo,P, f}, {a, b}, {A, B, Z}, 5, qo, Z, {f}), kde
5(qo,a, Z)	=	{(qo,AZ)}
5(qo,a, A)	=	{(qo,AA)}
5 (qo,a,B)	=	{(qo,AB)}
5 (qo,b,Z)	=	{(qo,BZ)}
5 (qo,b,A)	=	{(qo,BA)}
5 (qo,b,B)	=	{(qo,BB)}
5(qo,e, Z)	=	{(p,Z)}
5 (qo,e, A)	=	{(P, A)}
5 (qo,e,B)	=	{(p,B)}
5 (p, a, A)	=	{(P,e)}
5 (p, b, B)	=	{(P,e)}
5 (p,e,Z)	=	{(f,Z)}
IB102 Automaty a gramatiky, 22.11.2010
1
Příklad
M = ({qo}, {a, b}, {Z, A}, ô, qo, Z, 0), kde
ô(qo, a, Z) = {(qo, A)}
ô (qo,a,A) = {(qo,AA)} ô (qo,b, A) = {(qo,e)}
IB102 Automaty a gramatiky, 22.11.2010
2
Ekvivalence dvou způsobů akceptovaní
Veta 3.39.   Pro kaZdý jazyk L plat í:
L = L (N) pro nejaky PDA N        L = Le(M) pro nejaky PDA M.
Důkaz.  koncový štav       prazdný zašobník
Intuice:
K danemu N zkonstruujeme M simuluj íc í jeho Činnost.
Vejde-li N do koncoveho stavu, M se nedeterministicky rozhodne
• pokracovat v simulaci automatu N nebo
• prej ít do nove pridaneho stavu q£, v nemz vyprazdn í zasobn ík.
IB102 Automaty a gramatiky, 22.11.2010
3
Komplikace:
Řešení: pred zahájením simulace bude u M na dne zásobníku nový symbol, který nedovol íme odstranit jinde, neZ ve stavu q£.
IB102 Automaty a gramatiky, 22.11.2010
4
Konstrukce: Necht N = {Q, S, r, ô, q0, Z0, F).
Klademe M = {Q U {q0, q£} , S , r U {Z'} , ô', q0 , Z', 0), kde Z' G r, q0,qe G Q a ô' je definovaná takto:
• ô'{q0,e,Z') = {{q0, Z0Z')}
• jestliže ô {q, a, Z) obsahuje {r, 7), pak ô'{q, a, Z) obsahuje {r, 7)
• ô '{q, e, Z) obsahuje {q£,Z)
pro vsechny q G F a Z G r U {Z'}
• ô '(q£,£,Z) = {{q£
pro vsechny Z G r U {Z'}
IB102 Automaty a gramatiky, 22.11.2010
5
Korektnost:
IB102 Automaty a gramatiky, 22.11.2010
6
prázdný zásobník koncový stav Intuice:
K danému M zkonstruujeme N simulující jeho činnost.
• N si pred simulací prida na dno zásobníku nový symbol.
• Je-li N schopen číst tento symbol (tj. zasobník automatu M je prazdný) tak N prejde do nove pridaneho stavu qf, který je koncovým stavem.
IB102 Automaty a gramatiky, 22.11.2010
7
Konstrukce: Necht M = (Q, S,r, ô, q0, Z0,0).
Klademe N = (Q U {q0, q f} , S , r U {Z'} , ô', q'0 , Z', {qf}), kde Z' G r, q0, qf G Q a ô' je definovana takto:
• ô '(q'0,e,Z' ) = {(qo, Zo Z')}
jestlize ô (q, a, Z) obsahuje (r, 7), pak ô '(q, a, Z) obsahuje (r, 7)
• ô '(q, e, Z' ) = {(qf ,e)}
pro vsechny q G Q □
IB102 Automaty a gramatiky, 22.11.2010
8
Grafická reprezentace konfigurací
IB102 Automaty a gramatiky, 22. 11. 2010
g
Rozšírený zásobníkový automat
Definice 3.44.       Rozšírený zásobníkový automat je sedmice
R = (Q, S, T,ô,q0,Zo,F), kde
• vsechny symboly až na 5 mají tentýž význam jako v definici PDA,
• 5 je zobrazením
z koneCne podmnoZiný množiny Q x (S U {e}) x r* do koneCných podmnozin množiny Q x r*.
Pojmy konfigurace a akceptovany jazyk (koncovym stavem, prazdnym zásobníkem) zůstávají beze změny. Krok výpočtu \-^- definujeme takto:
(p,aw, jia)       (q,wH2&) <=> 3(g,72) G 5(p,a,7i) pro a G SU{^}
IB102 Automaty a gramatiky, 22.11.2010
10
Příklad
= ({qo,p, f}, {a,   c, d}, {A, B, Z}, 6, qo, Z, {/}), kde
6 (qo,a,e) 6 (qo,b,e) 6 (qo,e,e) 6 (p, a, A)
6 (p, b, B) 6 (p, c, AA)
6(p c BBB)=
6 (p, d, Z) =
{(qo,A)} {(qo,B)} {(p, e)} {(p, e)} {(p, e)} {(p, e)} {(p, e)}
{(f,e)}
IB102 Automaty a gramatiky, 22.11.2010
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, 22.11.2010
12
Důkaz. Necht 1Z = (Q, S, r, 5, q0, Z0, F) je rozšírený PDA a
m = max{|a| | 5(q, a, a) je definováno pro nejake q G Q, a G S U {č}}.
Definujeme P = (Qi, S, Ti, 5i, qi, Zi, F), kde
• Qi = {[q, a] | q G Q, a G ľj, 0 < |a| < m},
• ľi = ľ U {Zi}, kde Zi je nový šýmbol,
• qi = [qo,Zo z11-1],
• Fi = {[q, a] | q G F, a G ľj, 0 < |a| < m}.
IB102 Automaty a gramatiky, 22.11.2010
13
• Si je definovana takto:
- jestliže S(q, a, Xi... Xk) obsahuje (r, Yi... Yl), pak l > k
Si([q, Xi... Xka], a, Z) obsahuje ([r, /?], yZ), kde /?y = Yi... Ya a |/3| = m,
pro všechny Z £ ri a a £ 1^ takove, že |a| = m — k
l < k
Si([q, Xi... Xka], a, Z) obsahuje ([r, Yi... YaZ pro vsechny Z £ ri a a £ 1^ takove, že |a| = m — k
- Si([q,a],£,Z) = {([q,aZ],£)|
pro vsechny q £ Q, Z £ ri a a £     takove, že |a| < m
IB102 Automaty a gramatiky, 22.11.2010
14
Korektnost:  Ověříme, že platí
(g, aw, Xi... XkXk+1... Xn)      (r, w, Yí... Y^+i... Xn) ([g, a], aw, /?) |-^- ([r, a/], Z?7),
kde:
1. a/3 = Xi... Xn Zm,
2. afpf = Yi... YXk+i... XnZm,
3. |a| = \a'\ = m a
4. meži dvěma výše uvedenými konfiguracemi PDA P neexistuje takova konfigurace, kde druha komponenta stavu (tj. buffer) bý mela díelku m.
□
IB102 Automaty a gramatiky, 22.11.2010
15