Příklad
M = ({qo,p, f}, {a, b}, {A, B, Z}, S, q0, Z, {f}), kde
S(q0,a,Z) = {(q0,AZ)} 6(q0,a,A) = {(qQ,AA)} S(qo,a, B) = {{qQ,AB)} 5(q0lb,Z) = {(q0,BZ)} 5(qQ,b,A) = {(q0,BA)} S(qQ,b,B) = {(q0,BB)} 6{qo,e,Z) = {(p,Z)} S(qo,e,A) ={{p,A)} S(q0,e,B) ={(p,B)} S(p,a,A) ={(p,s)} S(p,b,B) ={(p,e)} 5(p,e,Z) ={(f,Z)}
IB102 Automaty a gramatiky, 25.11.2019
1/15
Příklad
M = ({q0}, {a, b}, {Z, A}, S, qQ, Z, 0), kde
S(q0,a,Z) = {(qQ,A)} S(q0,a,A)={(q0,AA)} S(qo,b,A) = {(qQ,e)}
IB102 Automaty a gramatiky, 25.11.2019
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, 25.11.2019 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, 25.11.2019
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, 25.11.2019
5/15
Korektnost:
IB102 Automaty a gramatiky, 25.11.2019
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, 25.11.2019
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, 25.11.2019
Grafická reprezentace konfigurací
IB102 Automaty a gramatiky, 25.11.2019
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, 25.11.2019
10/15
Příklad
n = ({q0l p, f}, {a, Ď, c, d}, {A, S, Z}, 5, q0, Z, {f}), kde
5((fo,a,e)
S(qo,e,e) S(p, a, 4)
«(P, b, B) S(p, c, AA) 5(p, c, BBB) S(P, d, Z)
{(Qo,B)}
{(P, e)} {(P, e)} {(P, e)} {(P, e)} {(P, e)} {(f, e)}
IB102 Automaty a gramatiky, 25.11.2019
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, 25.11.2019
12/15
Důkaz. Nechť n = (Q, Z, r, S, q0, Z0, F) je rozšířený PDA a
m = max{H | <5(q, a,«) je definováno pro nějaké g e Q, a e Z u {e}}.
Definujeme V = (Qi,Z, r-|,5i,gi,Zi,Fi), kde
■ Q1 = {[</, a] | g € O, a e Hf, 0 < \a\ < m},
■ n = r u {Zi}, kde Zi je nový symbol,
■ Fi
■ <7i
[QcZoZf-1],
{[<7, a] | q e F, a e r*, 0 < \a\ < m}.
IB102 Automaty a gramatiky, 25.11.2019
13/15
5-i je definována takto: - jestliže 5{q, a, X1 ... Xk) obsahuje (r, Y^... V/), pak
/ > k: 5i([g,X| .. .Xka],a,Z) obsahuje Qr,/3],7Z), kde /?7 = Y^ ... Y\ol a    = at?, pro všechny Z e l"i a a e    takové, že \a\ = m - k
I < k: 5^ ([g, X^ ... Xka],a, Z) obsahuje ([r, Ví ... Y\olZ\s)
pro všechny ZgH aaGT| takové, že - ^([qsa],^Z) = {([g,aZ],e)}
= m - k
pro všechny g e Q, Z e l"i a a e r* takové, že |a| < m
IB102 Automaty a gramatiky, 25.11.2019
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, 25.11.2019
15/15