Příklad
M = ({cio, p, f}, {a, b}, {A, B, Z}, S, q0, Z, {f}), kde
S(q0,a,Z) = {(q0,AZ)} S(qo,a,A) = {{q0,AA)} S(qo,a, B) = {{qQ,AB)} S(q0,b,Z) = {(q0,BZ)} S(qQ,b,A) = {(q0,BA)} S(q0,b,B) = {(q0,BB)} S{q0,s,Z) = {(p, Z)} ô(q0,e,A) ={(p,A)} S(qo,e,B) ={(p,B)} S(p,a,A) ={(p,e)} S(p,b,B) ={(p,e)} 5(p,e,Z) ={(f,Z)}
IB102 Automaty a gramatiky, 19.11.2018
1/15
Příklad
M = ({q0}, {a, b}, {Z, A}, ô, q0, Z, 0), kde
ó(q0,a,Z) = {(q0,A)} S(q0,a,A)={(q0,AA)} ô(q0,b,A) = {(q0,£)}
IB102 Automaty a gramatiky, 19.11.2018
2/15
Ekvivalence dvou způsobů akceptování
Věta 3.39. Pro každý jazyk L platí:
L = L(Af) pro nějaký PDA AT ^ L = Le(M) pro nějaký PDA M
Důkaz, koncový stav = prázdný zásobník Intuice:
K danému J\í zkonstruujeme M simulující jeho činnost.
Vejde-li J\í do koncového stavu, M se nedeterministicky rozhodne
■ pokračovat v simulaci automatu J\f nebo
■ přejít do nově přidaného stavu q£, v němž vyprázdní zásobník.
IB102 Automaty a gramatiky, 19.11.2018 3/15
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, 19.11.2018
4/15
Konstrukce: Nechť J\í = (Q, Z, r, 6, q0, Z0, F).
Klademe m = (Ou {tf0,Z, ru {Z7},tf0,Z',0), kde Z' ^ r, Qq, q£ ^ Q a (5; je definována takto:
■ 6'{(f0,e,Z') = {{qo,ZoZ')}
■ jestliže 5(q, a, Z) obsahuje (r, 7), pak 5'(q, a, Z) obsahuje (r, 7)
■ S'(q,e,Z) obsahuje (ge,Z)
pro všechny geFaZeru {Zř}
■ 8\qe,e,Z) = {(cfe,e:)} pro všechny ZgTu {Z7}
IB102 Automaty a gramatiky, 19.11.2018
5/15
Korektnost:
IB102 Automaty a gramatiky, 19.11.2018
6/15
prázdný zásobník =4> koncový stav Intuice:
K danému M zkonstruujeme J\í simulující jeho činnost.
■ J\f si před simulací přidá na dno zásobníku nový symbol.
■ Je-li J\f schopen číst tento symbol (tj. zásobník automatu M je prázdný) tak J\f přejde do nově přidaného stavu qf, který je koncovým stavem.
IB102 Automaty a gramatiky, 19.11.2018
7/15
Konstrukce: Nechť M = (Q, E, l~, S, q0, Z0,0).
Klademe JV = (Ou {tf0, gř}, Z, r u {Z'}, 5', q'Ql Z', {g,}), kde Z'   r, <7q, qy ^ Q a 5' je definována takto:
■ 5'(q'0,s,Z>) = {(q0,Z0Z>)}
■ jestliže S(q, a, Z) obsahuje (r, 7), pak 5'(qf, a, Z) obsahuje (/-, 7)
■ 5'{q,e,Z') = {{qf,e)} pro všechny qeQ
IB102 Automaty a gramatiky, 19.11.2018
Grafická reprezentace konfigurací
IB102 Automaty a gramatiky, 19.11.2018
9/15
Rozšířený zásobníkový automat
Definice 3.44. Rozšířený zásobníkový automat je sedmice
^ = (Q,Z,r,(5,Q0,Z0,F)5kde
■ všechny symboly až na S mají tentýž význam jako v definici PDA,
■ S je zobrazením
z konečné podmnožiny množiny Q x (Z u {s}) x r* do konečných podmnožin množiny Q x r*.
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:
def
(p,aw,^a) h?-(<7, w,72a) ^ 3(9,72) e <5(P,a,7i) pro aeHu{e}
IB102 Automaty a gramatiky, 19.11.2018
10/15
Příklad
n = ({q0, p, f}, {a, b, c, d}, {A, B, Z}, S, q0, Z, {f}), kde
S(qo,a,e) S(q0,b,s)
S (p, a, A)
S(P, b, B) ô (p, c,AA) S(p, c, BBB) S(p, d, Z)
{(Qo,A)}
{(P, e)} {(P, e)} {(P, e)} {(P, e)} {(P, e)} {(f,e)}
IB102 Automaty a gramatiky, 19.11.2018
11/15
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, 19.11.2018
12/15
Důkaz. Nechť n = (Q, z, r, S, q0l z0, F) je rozšírený PDA a
m = max{|a| |      a, a) je definováno pro nějaké q g q, a g z u {č}}.
Definujeme p = (Qi, z, ^, ^, q1, z|, F|), kde
■      = {[q, a] | Q g Q, a g ľ*, 0 < |a| < a7?},
m ľ-i =ru{z1}, kde z| je nový symbol,
■ F!
[Qo^oZj77-1],
{[Q, a] | Q g F, a g ľ*, 0 < \a\ < m}.
IB102 Automaty a gramatiky, 19.11.2018
13/15
Si je definována takto: - jestliže 5(q, a, X1 ... Xk) obsahuje (r, Yí ... Y/), pak
/ > k\ .. .Xkoi\,a,Z) obsahuje Qr,/3],7Z),
kde /37 = V^i ... Y/a a |/3| = m5 pro všechny Z e r1 a a e    takové, že |a| = rn - k
I < k: 51 ([q,X1 ...Xka],a,Z) obsahuje ([r,    ... Y\olZ\s) pro všechny Z e r1 a a e    takové, že \a\ = rn - k
- 6i([q,a],e,Z) = {([q,aZ\,e)}
pro všechny q e Q, Z e r1 a a e V] takové, že \a\ < m
IB102 Automaty a gramatiky, 19.11.2018
14/15
Korektnost: Ověříme, že platí
(<7, aw, Xi ... X/fX/^i ... Xn) |-^- (r, tv, Ví ... V/X^+i ... Xn) ^ ([q,a],aw,/3)\^-([r,a'],w,p'),
kde
a/3 = X\ .. a'/3' = V-, .
' m
a
a'
• • V//X/c+1 = m a
mezi dvěma výše uvedenými konfiguracemi PDA P neexistuje taková
konfigurace, kde druhá komponenta stavu (tj. buffer) by měla
délku m. □
IB102 Automaty a gramatiky, 19.11.2018
15/15