Příklad
M = {{qo,p, f}, {a, b}, {A, B, Z}, S, q0, Z, {f}), kde
%o
%0
%o
%o
%o
%o
%o S (q
a, Z)
b, Z)
a, A)
b, A)
a, B)
b, B) e, Z) e, A) e, B)
5 (p, a, Ä) 5(p, b, B) ô(p,s,Z)
o
{(40 {(40 {(40
{(4o
{(4
{(4o
= 1 4o
AZ)} BZ)} A A)} BA)} AB)} BB)}
{{P, Z)} {(P, A)} {(P, B)} {(P, e)} {(P, e)} {(f, Z)}
IB102 Automaty a gramatiky, 30.11.2009
Příklad
M = ({go}, {a, &}, {Z, A}, ô, g0, Z, 0), kde
ô(q0,a,Z) = {(g0, A)} ö(q0,a,A) = {(q0,AA)} S(q0,b,A) = {(g0,e)}
IB102 Automaty a gramatiky, 30.11.2009
2
Ekvivalence dvou způsobů akceptování
Věta 3.39.   Pro každý jazyk L platí:
L = L(Af) pro nějaký PDA Aí ^^ L = Le(M) pro nějaký PDA A4.
Důkaz,   koncový stav => prázdný zásobník
Intuice:
K danému Aí zkonstruujeme A4 simulující jeho činnost.
Vejde-li N do koncového stavu, A4 se nedeterministicky rozhodne
•  pokračovat v simulaci automatu Aí nebo
•  přejít do nově přidaného stavu q£, v němž vyprázdní zásobník.
IB102 Automaty a gramatiky, 30.11.2009
3
Komplikace:
Řešení:   před zahájením simulace bude u Aí na dně zásobníku nový symbol, který nedovolíme odstranit jinde, než ve stavu q£.
IB102 Automaty a gramatiky, 30.11.2009
4
Konstrukce: Necht N = (Q, E, T, ô, q0, Z0, F).
Klademe M = (Q U {q'0, qs] , S , T U {Z'} , ô', q'0 , Z', 0), kde Z' ^ T, qQ,q£ ^ Q a 5' je definována takto:
•  jestliže 8{q,a,Z) obsahuje (r, 7), pak 5'(q, a, Z) obsahuje (r, 7)
•  8'{q,e,Z) obsahuje (q£,Z)
pro všechny qe F a Z eVU {Z'}
•  S'(qe,e,Z) = {(qe,e)} pro všechny Z G T U {Z'}
IB102 Automaty a gramatiky, 30.11.2009
5
Korektnost:
IB102 Automaty a gramatiky, 30.11.2009
6
prázdný zásobník => koncový stav Intuice:
K danému A4 zkonstruujeme J\í simulující jeho činnost.
•  J\í si před simulací přidá na dno zásobníku nový symbol.
•  Je-li Áí schopen číst tento symbol (tj. zásobník automatu M je prázdný) tak A/- přejde do nově přidaného stavu qf, který je koncovým stavem.
IB102 Automaty a gramatiky, 30.11.2009
7
Konstrukce: Necht M = (Q,Y,,r,ö,q0,Z0,®).
KlademejV=(QU{g/0,í/},S,ru{Z/},(y/,g/0,Z/,{í/})1 kde Z' ^ T, q^qf £ Q a 8' je definována takto:
. ô'(q'0,e,Z') = {(qo,Z0Z')}
• jestliže 5(g, a, Z) obsahuje (r, 7), pak 57(g,a, Z) obsahuje (r, 7)
.ô'(q,e,Z') = {(qf,e)} pro všechny g G Q
IBIO2 Automaty a gramatiky, 30.11.2009
8
Grafická reprezentace konfigurací
IB102 Automaty a gramatiky, 30.11.2009
9
Rozšírený zásobníkový automat
Definice   3.44.          Rozšírený   zásobníkový   automat  je   sedmice
n= (Q, E, T, č, qo,Z0,F), kde
•  všechny symboly až na 5 mají tentýž význam jako v definici PDA,
•  5 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 T*.
Pojmy konfigurace a akceptovaný jazyk (koncovým stavem, prázdným zásobníkem) zůstávají beze změny. Krok výpočtu \-^- definujeme takto:
7        P
(p, aw, jio)   h^ (tf? w? 72^) <=> 3(9,72) G 5(p,a,7i) pro a G SU{^}
IBIO2 Automaty a gramatiky, 30.11.2009
10
Příklad
ft = ({Qo,P, /}, {a, b, c, d}, {A, B, Z}7 5, q0, Z, {/}), kde
%o,a,e)      ={
%o,M)      ={
ô(q0,e,e)       ={
ô(p, a, A)       = {
S(p, b, B)       ={
5(p, c, AA)    = {
S(p, c, BBB) = {
ô(p, d, Z)       = {
qo,A)}
qo,B)}
} } } } } }

IB102 Automaty a gramatiky, 30.11.2009
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, 30.11.2009
12
Důkaz. Necht TZ = (Q, S, T, 5, g0, ^o? F) je rozšírený PDA a
m = max{|ce| | 5(g, a, a) je definováno pro nějaké g G Q, a G S U {č}}
Definujeme P = (Qi, £,]ľi, 5i,gi, Z\,F\), kde
•  Qi = {[g, a] | g G Q, a G rj, 0 < \a\ < m},
•  Ti = T U {^i}, kde Z\  je nový symbol,
. q1 = [q0,Z0Z™-1},
•  Fi = {[g, a] | g G F, ce G rj, 0 < |a| < m}.
IB102 Automaty a gramatiky, 30.11.2009
13
öi  je definována takto:
jestliže 5(g, a, X\... Xk) obsahuje (r, li... Y/), pak Z>fc
5i([g,Xi... Xfea],a, Z) obsahuje ([r,ß\,^Z),
kde /?7 = li... Y/a a |/3| = m,
pro všechny Z G Ti a ce G rj takové, že
ce
— vn —
k
l<k
öi([q,Xi... Xfea],a, Z) obsahuje ([r, Yi... YiaZ\,é) pro všechny Z G Ti a a G TJ takové, že |a| = m — k
öi([q,a],e,Z) = {([g,aZ],e)}
pro všechny q G Q, Z G Ti a ce G TI takové, že \a\ < m
IB102 Automaty a gramatiky, 30.11.2009
14
Korektnost:   Ověříme, že platí
(g, aw, X\... XkXk+i... Xn)
^^>  ([g, a], aw,ß) |-p-(
r, ar
w,/3'),
• YlXk+l - - - -X'n)
kde:
1.   Qífj — X\ . . . Xn/j^   ,
2. a /? — Yi... Y^Xfc+i... XnZf\
3.
a
a
= m  a
4. mezi dvěma výše uvedenými konfiguracemi PDA V neexistuje taková konfigurace, kde druhá komponenta stavu (tj. cache) by měla délku m.
D
IB102 Automaty a gramatiky, 30.11.2009
15