Příklad
M = {{qo,p, f}, {a, b}, {A, B, Z}, 5, q0, Z, {/}), kde
S(q0,a,Z) = {(q0,AZ)} S(qQ,a,A) = {(q0,AA)} 6{qo,a, B) = {(q0,AB)} 5(q0,b,Z) = {(q0,BZ)} 5(q0,b,A) = {(qQ,BA)} S(q0,b, B) = {(q0,BB)} S(q0,e,Z) = {(p,Z)} S(q0,e,A) ={(p,A)} S(q0,s,B) = {(p,B)} S(p,a,A) ={(p,e)} S(p,b,B) ={(p,e)} 5(p,e,Z) ={(f,Z)}
IB102 Automaty, gramatiky a složitost, 9.11.2015
1/27
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, gramatiky a složitost, 9.11.2015
2/27
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 =4> 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, gramatiky a složitost, 9.11.2015
3/27
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, gramatiky a složitost, 9.11.2015
4/27
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, gramatiky a složitost, 9.11.2015
5/27
Korektnost:
IB102 Automaty, gramatiky a složitost, 9.11.2015
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, gramatiky a složitost, 9.11.2015
7/27
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 S'(q, a, Z) obsahuje (r, 7)
■ 5'{q,e,Z') = {{qf,e)} pro všechny q e Q
IB102 Automaty, gramatiky a složitost, 9.11.2015
Grafická reprezentace konfigurací
IB102 Automaty, gramatiky a složitost, 9.11.2015
9/27
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, gramatiky a složitost, 9.11.2015
10/27
Příklad
n = {{q0,p, f}, {a, b, c, d}, {A, B,Z},S, q0,Z, {f}), kde
ô(qo,a,e) ={(q0,A)}
S(q0,b,s) = {(q0,B)}
S(qo,s,e) ={(p,e)}
S(p,a,A) = {(p,e)}
S(p,b,B) ={(p,e)}
6{p,c,AA) ={(p,e)} S(p,c,BBB) = {(p,e)}
6(p,d,Z) ={(f,e)}
IB102 Automaty, gramatiky a složitost, 9.11.2015
11/27
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, gramatiky a složitost, 9.11.2015
12/27
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 = r u {z|}, kde z| je nový symbol,
■ F!
[QcZoZ^-1],
{[Q, a] | Q g F, a g ľ*, 0 < \a\ < m}.
IB102 Automaty, gramatiky a složitost, 9.11.2015
13/27
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, gramatiky a složitost, 9.11.2015
14/27
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, gramatiky a složitost, 9.11.2015
15/27
Zásobníkové automaty a bezkontextové jazyky
	Lemma 3.45	PDA		PDA
rozšířené		akceptující	Věta 3.39	akceptující
				
PDA		koncovým		prázdným
	triviálně			
		stavem		zásobníkem
CFG
IB102 Automaty, gramatiky a složitost, 9.11.2015
16/27
Zásobníkové automaty a bezkontextové jazyky
Motivace 1: Jaká je třída jazyků rozpoznávaných zásobníkovými automaty?
Motivace 2: Je dána bezkontextová gramatika Q a slovo w. Jak zjistit, zda se slovo w dá vygenerovat v gramatice Q?
Problém syntaktické analýzy pro bezkontextové gramatiky:
pro danou bezkontextovou gramatiku Q a slovo w rozhodnout, zda w g L(Q).
IB102 Automaty, gramatiky a složitost, 9.11.2015
17/27
Ekvivalence bezkontextových gramatik a
zásobníkových automatů
Věta 3.51. Ke každému PDA M lze sestrojit CFG Q takovou, že
Le{M) = L(gy
Důkaz. Vynechán. □
Věta 3.47. Ke každé CFG Q lze sestrojit PDA M takový, že L{Q) = Le{M).
Důkaz. Uvedeme za chvíli. □
Důsledek 3.52. Třída jazyků rozpoznávaných zásobníkovými automaty je právě třída bezkontextových jazyků.
IB102 Automaty, gramatiky a složitost, 9.11.2015
18/27
Intuice převodu PDA na CFG
1.0=1
IB102 Automaty, gramatiky a složitost, 9.11.2015
19/27
Intuice převodu PDA na CFG
2. O > 2
IB102 Automaty, gramatiky a složitost, 9.11.2015
20/27
Intuice převodu CFG na PDA
Konstrukce PDA řeší problém syntaktické analýzy. (Platí pro dané Q a w\ w e L(Q)?)
w g L{Q) <=^> v g existuje derivační strom s výsledkem w
IB102 Automaty, gramatiky a složitost, 9.11.2015
21/27
Intuice převodu CFG na PDA aneb O nedeterministické syntaktické analýze
PDA se bude snažit budovat derivační strom pro w.
shora dolů
zdola nahoru
IB102 Automaty, gramatiky a složitost, 9.11.2015
22/27
Intuice pro analýzu shora dolů
Budování derivačního stromu simuluje levé derivace, tj. vždy rozvíjíme nejlevější neterminál.
IB102 Automaty, gramatiky a složitost, 9.11.2015
23/27
Nedeterministická syntaktická analýza shora dolů
Věta 3.47. Ke každé CFG Q lze sestrojit PDA M takový, že L{Q) = Le{M).
Důkaz. K dané gramatice Q konstruujeme PDA M, který simuluje levé derivace v g.
■ V levé derivaci je v jednom kroku odvození nahrazen (nejlevější) neterminál A pravou stranou X1 ... Xn nějakého /A-pravidla.
i VM této situaci odpovídá náhrada A na vrcholu zásobníku řetězem X-\ ... Xn.
M = ({q}, Z, N u Z, S, q, S, 0), kde S je definována:
■ 5(q, e, A) obsahuje (g, a) právě když A^ř a e P m 5(q, a, a) = {(g, e)} pro všechna a g Z
IB102 Automaty, gramatiky a složitost, 9.11.2015
24/27
c ^ *AR 6{q,e,S) = {{q,aAB)}
R^SaMb 8{g,e,B) = {(q,SaA),(q,b}
B -» SaA w       =      fo fo) = £)}
S a/4B afí =>• aSa/4 =>• aa/ASa/A aa6a/A aaĎa/A aaĎa
IB102 Automaty, gramatiky a složitost, 9.11.2015
25/27
Korektnost
(=4>) Indukcí vzhledem k délce odvození m.
■ m = 1: zřejmé.
■ m > 1: nechť tvrzení platí pro všechna mí < m.
A =4> X1X2 ... Xk =4>* x1 x2 ... X/c = i/i/, kde X, ^ x/5 0 < irij < m z definice 5 plyne (q, i/i/,/4) |—(q, i/i/,X|X2 .. . X/c).
Je-li X, g A/, pak dle indukčního předpokladu máme
(q,X/,X/) {^(q,s,s).
Je-li X, g Z, pak X, = x, a z definice 5 plyne (q, x,, x,) |— (q, e, e). Kompozicí dostáváme (q, i/i/, /4) p^- (g? ^
IB102 Automaty, gramatiky a složitost, 9.11.2015
26/27
(<==) Předpokládejme (q, 1/1/, A) |— (q, e, e) a ukažme /4 =4>+ 1/1/. Indukcí vzhledem k délce výpočtu n.
■ n = 1: zřejmé.
■ n > 1: nechť tvrzení platí pro všechna rí < n.
(q, i/M)        w,X1X2...X/f)J tj.       X1X2. ..X/c e P
i/i/ můžeme napsat jako w = x-|X2 ... xk takové, že
■ je-li Xj e A/, pak (q, x,, X,) p^- (q, e, e), kde n, < n. Dle IP X, ^+ X,.
■ je-li X, e 51, pak X, 4> x,.
Vhodnou kompozicí obdržíme
A =4> X1X2 ... X/c =4>* x1 X2 ... X/c =4>* x1 ... X/c = i/i/ což je levá derivace slova w v gramatice
IB102 Automaty, gramatiky a složitost, 9.11.2015