Příklad
M = ({c?o,p,    {a, b}, {A B,Z},S, q0,Z, {f}), kde
S(qo,a,Z) = {{q0,AZ)} S(q0,a,A) = {(q0,AA)} S(qQ,a, B) = {(q0,AB)} S(q0,b,Z) = {(q0lBZ)} S(q0,b,A) = {(q0,BA)} S(qo,b, B) = {(qQ,BB)} S(q0,e,Z) = {(p,Z)} S(qo,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, gramatiky a složitost, 9.11.2015
1/27
Přiklad
M = ({<*>}, {a, b}, {Z, A}, ô, qQ,Z, 0), kde
ó(q0,a,Z) = {(q0,A)} S(q0,a,A) ={(q0,AA)} S(q0,b,A) = {(q0je)}
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(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, cfo, Z0, F).
Klademe m = (Ou {g£,     Z, r u {Z'},tf0,Z',0), kde Z7 ^ r, Qq, q£ ^ Q a (57 je definována takto:
■ 6\(&,e,Z') = {{qo,ZoZ')}
■ jestliže 8(q, a, Z) obsahuje (r, 7), pak 8\q, a, Z) obsahuje (r, 7)
■ 8\q,e,Z) obsahuje (<fe,Z)
pro všechny QGfaZGTu {Z7}
■ 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, r, l~, S, q0, Z0,0).
Klademe JV = (Ou {cfQl qf}, Z, r u {Z'}, 6', cf0, Z, {qf}), kde Z'   r, <7q,   ^ Q a 5' je definována takto:
■ 5>(cf0,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
■ 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=-(qr, w,72a) ^ 3(9,72) e S(p, a,7l) pro aeHu{e}
IB102 Automaty, gramatiky a složitost, 9.11.2015
10/27
Příklad
n = ({Qo,P, f}, {a, b, c, d}, {A, B,Z},S, q0,Z, {f}), kde
5(q0,a,e) ={(q0,A)}
S(q0,b,s) ={(q0,B)}
S(qQ,s,e) ={(p,e)}
S(p,a,A) ={(p,e)}
S(p,b,B) ={(p,e)}
S{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, ^, ^, g1, Z|, F|), kde
■ Ql = {[q, a] | q g Q, a g ľ*, 0 < |a| < a7?},
■ r-i = r u {Z|}, kde Z| je nový symbol,
[Qo,Z0Z^-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\ 51([q,X1 .. .Xka],a,Z) obsahuje Qr,/3],7Z), kde /fy =    ... V/a a |/3| = rn, pro všechny Z e r1 a a e    takové, že \a\ = rn - k
I < k: 51 ([qr, X1 ... Xka],a, Z) obsahuje ([r, Y^ ... Y\olZ\s) pro všechny Z e r1 a a e    takové, že |a| = m - k
- 6i([q,a],e,Z) = {([q,aZ\,e)}
pro všechny g e Q, Z e r1 a a e    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, w, Ví ... V/X^+i ... Xn) ^  ([q, a], aw713) \±- ([/-,«'], w,p'),
kde
a/3 = X| .. a'/3' = V-, .
'/T7
a'
= A77 a
mezi dvěma výše uvedenými konfiguracemi PDA V 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ě			
		stave m		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é gaw.we L(G)7)
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.
■ V M této situaci odpovídá náhrada A na vrcholu zásobníku řetězem
yc-\... x^.
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     aAR 5{q,e,S) = {{q,aAB)}
R^SaMb 5(q,e,B) = {{q,SaA),(q,b)}
B     SaA 1 Ó 5(q, a, a) =      b, b) = {(q, e)}
S a/AS => aB ^> aSaA ^> aaABaA aaBaA aabaA aaba
IB102 Automaty, gramatiky a složitost, 9.11.2015
25/27
Korektnost
(=4>) Indukcí vzhledem k délce odvození m.
■ m = 1: zřejmé.
■ a77 > 1: nechť tvrzení platí pro všechna ni < m.
A =4> X1X2 ... Xk =4>* x1 x2 ... xk = w, kde X, ^ x/5 0 < m, < m z definice 5 plyne (g, w,/4) |—(g, i/i/,X|X2 .. .X^).
Je-li X, g A/, pak dle indukčního předpokladu máme
(g,X/,X,) [^(q,e,e).
Je-li Xj g Z, pak X,- = x, a z definice 5 plyne (g, x,, x,) |— (g, e, e). Kompozicí dostáváme (g, w, A)     (g, e, e).
IB102 Automaty, gramatiky a složitost, 9.11.2015
26/27
(<==) Předpokládejme (qr, w, A)     (qr, e, e) a ukažme A =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.
(qr, i/M) |—(qr, w,X|X2 . ..Xk), tj. /A    XjX2 ...XkeP
w můžeme napsat jako w = x-|X2 ... xk takové, že
■ je-li Xj e N, pak (q, x,, X,) p^- (q, e, e), kde n,- < n. DlelPX/^+x,.
■ je-li X,- e 51, pak X,- 4> x,.
Vhodnou kompozicí obdržíme
/A =4> X1X2 ... Xk =4>* x1 X2 ... Xk =4>* X| .. .xk = i/i/ což je levá derivace slova w v gramatice g.
IB102 Automaty, gramatiky a složitost, 9.11.2015