Rozšírený zásobníkový automat
Definice 3.44.       Rozšírený zásobníkový automat je sedmice
K=(Q,'Ľ,r,6,q(hZo,F), kde
• všechny symboly až na ô mají tentýž význam jako v definici PDA,
• ô 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 r*.
Pojmy konfigurace a akceptovaný jazyk (koncovým stavem, prázdným
^- definujeme
zásobníkem) zůstávají beze změny.   Krok výpočtu
takto:
(q, w,j2oí) 4=> =1(2,72) G 5(p,a,7i) pro a £ SU{e}
(p, <m>, 71a)
IB102 Automaty, gramatiky a složitost, 11.11.2013
1
Příklad
= ({Qo,P, f}, {a, b, c, d}, {A, B, Z}, ô, q0, Z, {/}), kde
ô(q0,a,e) = {(q0,A)}
S(q0,b,e) ={(q0,B)}
S(q0,e,e) = {(p,e)}
S(p,a,A) = {(p,e)}
S(p,b,B) ={(p,e)}
S(p,c,AA) ={(p,e)} ô(p,c,BBB)= {(p,e)}
S(p,d}Z) ={(/,£)}
IB102 Automaty, gramatiky a složitost, 11.11.2013
2
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, gramatiky a složitost, 11.11.2013
3
Důkaz. Necht K = (Q, E, I\ ô, qQ, Z0, F) je rozšírený PDA a
m = max{|a| |      a, a) je definováno pro nějaké q G Q, a G S U {e}}
Definujeme P = (Qi,£,ri,5i,gi,Zi,Fi), kde
< m},
Qi = {[qM \qeQ, a e H, 0<
rx = r U {Zi}, kde Zi je nový symbol,
r r7   ryTYl— 1"
Fi = {[g, a] | g G F, a G TJ, 0 < |a| < m}.
IB102 Automaty, gramatiky a složitost, 11.11.2013
4
Si je definována takto:
jestliže 5(q, a, X\... Xk) obsahuje (r, Y\... Y/), pak l > k
5i([q, X\... -Xfca], a, Z) obsahuje ([r, /3],7Z), kde /?7 = Yi... Y/a a     = rn, pro všechny Z G Ti a a G r* takové, že
— m —
k
l < k
5i([q, X\... X^a], a, Z) obsahuje ([r, Yi... Y\olZ\,s) pro všechny Z G I\ a a G     takové, že |a| = m — /c
Si([q,oi\,e,Z) = {([g,aZ],e)}
pro všechny q G Q, Z G I\ a a G r* takové, že |a| < m
IB102 Automaty, gramatiky a složitost, 11.11.2013
5
Korektnost:  Ověříme, že platí
(g, aw, X\... XkXk+i... Xn)
^> ([g, a], au;, /3) ^-(
r, a
^(r,w, Yi
• YiXk+i • • • Xn)
kde:
1.      — X\... -X^iv]71,
2. a//^ — Yi... Y/Xfc+i... XnZf\
a'
= m a
4. 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, 11.11.2013
6
Zásobníkové automaty a bezkontextové jazyky
rozšírené
PDA
Lemma 3.45
triviálně
PDA akceptující koncovým stavem
Věta 3.39
Věta 3.39
PDA akceptující prázdným zásobníkem
CFG
IB102 Automaty, gramatiky a složitost, 11.11.2013
7
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 slovo w sa dá vygenerovat v gramatice Ql
Problém syntaktické analýzy pro bezkontextové gramatiky:
pro danou bezkontextovou gramatiku Q a slovo w rozhodnout,
zda w £ L(Q).
IB102 Automaty, gramatiky a složitost, 11.11.2013
8
Ekvivalence bezkontextových gramatik a zásobníkových automatů
Věta 3.51.    Ke každému PDA Ai lze sestrojit CFG Q takovou, že
Le(M) = L(G).
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, 11.11.2013
9
Intuice převodu PDA na CFG
1. Q =1
IB102 Automaty, gramatiky a složitost, 11.11.2013
10
Intuice převodu PDA na CFG
2. Q >2
IB102 Automaty, gramatiky a složitost, 11.11.2013
11
Intuice převodu CFG na PDA
Konstrukce PDA řeší problém syntaktické analýzy, (platí pro dané Q a w: w £ L{Q)1)
w £ L (Q) v Q existuje derivační strom s výsledkem w
IB102 Automaty, gramatiky a složitost, 11.11.2013
12
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, 11.11.2013
13
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, 11.11.2013
14
Nedeterministická syntaktická analýza shora dolů
Věta 3.47.      Ke každé CFG Q lze sestrojit PDA M takový, že
L(g) = Le(M).
Důkaz. K dané gramatice Q konstruujeme PDA A4, který simuluje levé derivace v Q.
• V levé derivaci je v jednom kroku odvození nahrazen (nejlevější) neterminál A pravou stranou X\.. ,Xn nějakého A-pravidla.
• V Ai této situaci odpovídá náhrada A na vrcholu zásobníku řetězem Xi... Xn.
M = ({q}, S,iVUS, 5, g, iS, 0), kde ô je definována:
• S(q,e, A) obsahuje (g, a) právě když A —> a £ P
• ô(q,a,a) = {(q, e)} pro všechna a G S
IB102 Automaty, gramatiky a složitost, 11.11.2013
15
s
A B
aAB Aa Sa A
£
ô(q,e,S) ö(q,e,A) ö(q,e,B) ô(q, a, a)
{(q, aAB)} {(q, Aa),(q,e)} {(q, SaA),(q,b)}
= {(q, e)}
S
aAB
aB
aSaA
aaABaA
aaBaA
aabaA
aaba
IB102 Automaty, gramatiky a složitost, 11.11.2013
16
Korektnost
(=>>) Indukcí vzhledem k délce odvození m.
1. m = 1: zřejmé.
2. m > 1: necht tvrzení platí pro všechna m' < m.
m i
A ... Xk      X1X2 .. .Xk = w, kde Xi =^ Xi, 0 < rrii < m
z definice 5 plyne (g, tu, A) |— (g, tu, ...
Je-li Xi G iV, pak dle indukčního předpokladu máme
Je-li     G E, pak Xi = 2^ a z definice 5 plyne (g, a^, 2^) |— (g, £, e)
Kompozicí dostáváme (g, £, £)■
IB102 Automaty, gramatiky a složitost, 11.11.2013
17
(<=) Předpokládejme (q,w,Á) p-(9, e, é) a ukažme A =^>+ w. Indukcí vzhledem k délce výpočtu n.
1. n = 1: zřejmé.
2. n > 1: necht tvrzení platí pro všechna n' < n.
(q,w,A) \—(q,w,X1X2...Xk), tj. A -> XľX2 ... X& G P
ii; můžeme napsat jako u> = ^1^2 .. .Xk takové, že
• je-li Xi G N, pak (q^x^Xi) p*-kde     < n.
Dle IP ^+
je-li Xi G S, pak Xi 4> 2^
Vhodnou kompozicí obdržíme
A X1X2 ... Xk ^1X2 ... Xk xi.. .Xk = w což je levá derivace slova w v gramatice C/.
IB102 Automaty, gramatiky a složitost, 11.11.2013
Intuice pro analýzu zdola nahoru
IB102 Automaty, gramatiky a složitost, 11.11.2013
19
Intuice pro analýzu zdola nahoru
IB102 Automaty, gramatiky a složitost, 11.11.2013
20
Nedeterministická syntaktická analýza zdola nahom
Věta 3.55. Necht Q je libovolná CFG, pak lze zkonstruovat rozšírený PDA n takový, že L {Q) = L(K).
Důkaz. Vrchol zásobníku píšeme vpravo.
Konstruujeme rozšírený PDA 1Z, který simuluje pravou derivaci v Q v obráceném poradí.
PDA 1Z má kroky dvojího typu:
1. může kdykoli číst do zásobníku vstupní symbol,
2. (redukce) je-li na vrcholu zásobníku řetěz tvořící pravou stranu nějakého pravidla v Q, může ho nahradit odpovídajícím levostranným neterminálem (a ze vstupu nic nečte).
IB102 Automaty, gramatiky a složitost, 11.11.2013
21
Necht G = (iV,S,P,5).
Položme TI = ({g,r},£,iV U S U {±},5,q, ±,{r}), kde JL je nově přidaný symbol a kde ô je definována takto:
1. 8(q,a,é) — {(g, a)} pro všechna a £ E,
2. je-li A —>> a, pak 5(g,£,a) obsahuje (g, A),
3. «5(g,e,±S) = {(r,e)}.
IB102 Automaty, gramatiky a složitost, 11.11.2013
22
krok výpočtu odpovídající pravidlo z Q
(q, i + i * i, _l)	i	(q, +i * i,		±»)	F -> i
	£	■fa, +	z * i,	_lf)	T -> F
	£	■(9, +	z * i,	_lt)	E t
	£		z * i,	±f)	
	+		z * i,	±f+)	
	i		*i,	±f + i)	f -> i
	£		*i,	±f + f)	T -r F
	£		*i,	±f + t)	
	*		i,	±f + t*)	
	i			±f + t * i)	F -> i
	£			_LE + T*F)	r —> t * f
	£		e,	-LE + T)	f -> f + t
	£		e,	±E)	
	£			e)	
Korektnost
S =^>* aAy => xy (g, xy, _L) p- (g, _LaA)
kde S =^>* aAy =S> xy je pravá derivace a A je nejpravější neterminál
(=>>) indukcí k délce odvození (^=) indukcí k délce výpočtu
Pro A = S a a,y = e dostáváme:
S =^>* x (g,   _L) p-(g, £, J_aÍ>)
(r,e)
'Výstupem" je pravá derivace v obráceném pořadí.
□
IB102 Automaty, gramatiky a složitost, 11.11.2013
24
Efektivnost syntaktické analýzy
Nederministický PDA =^> nedeterministický algoritmus =^> exponenciální deterministický algoritmus
Řešení:
• deterministický algoritmus složitosti (9(n3)ř kde n — \w (algoritmus Cocke - Younger - Kasami)
• deterministické zásobníkové automaty a deterministické bezkontextové jazyky
• lineární algoritmy pro speciální třídy deterministických bezkontextových jazyků
IB102 Automaty, gramatiky a složitost, 11.11.2013
25