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 a gramatiky, 2.12.2019
1/19
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 a gramatiky, 2.12.2019
2/19
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 a gramatiky, 2.12.2019
3/19
Intuice převodu PDA na CFG
1.0=1
IB102 Automaty a gramatiky, 2.12.2019
4/19
Intuice převodu PDA na CFG
2. O > 2
IB102 Automaty a gramatiky, 2.12.2019
5/19
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 a gramatiky, 2.12.2019
6/19
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 a gramatiky, 2.12.2019
7/19
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 a gramatiky, 2.12.2019
8/19
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 a gramatiky, 2.12.2019
9/19
c ^ aAR 6{q,e,S) = {{q,aAB)}
R^SaMb 8{g,e,B) = {(q,SaA),(q,b}
B     SaA 1 b ô\l a, a) =       b, b) = {(Q, e)}
S a/Aß aß =>• aSa/A =>• aaABaA aaBaA aabaA aaba
IB102 Automaty a gramatiky, 2.12.2019
10/19
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 ... xk = i/i/, kde X, ^ x/5 0 < m, < m z definice S 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,^).
Je-li Xj g Z, pak X, = x, a z definice S plyne (q, xh x,) |— (q, e, e). Kompozicí dostáváme (q, i/i/, /4) p^- (q, e, e).
IB102 Automaty a gramatiky, 2.12.2019 11/19
(<=) Předpokládejme (q, w. A) |— (q, e, e) a ukažme /A =>+ 1/1/. Indukcí vzhledem k délce výpočtu n.
■ n = 1: zřejmé.
■ n > 1: nechť tvrzení platí pro všechna /f < n.
(q, i/M) |—(q, w,X,X2 .. .Xk), tj. >4    ^X2 ...XkeP
w můžeme napsat jako w = x-|X2 ... xk takové, že
■ je-li Xj e A/, pak (q, x,, X,)     (q, e, e), kde n,- < n. Dle IP X, ^+ x,.
■ je-li Xj e 51, pak X, 4> x,.
Vhodnou kompozicí obdržíme
A    X1X2 ... Xk =4>* x1 X2 ... Xk =>* x1 ...xk = i/i/
což je levá derivace slova w v gramatice c?.
IB102 Automaty a gramatiky, 2.12.2019
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 2.12.2019
13/19
Intuice pro analýzu zdola nahoru
S XY
X ->• ab
Y ->• c
IB102 Automaty a gramatiky, 2.12.2019
14/19
Nedeterministická syntaktická analýza zdola nahoru
Věta 3.55. Nechť Q je libovolná CFG, pak lze zkonstruovat rozšířený PDA takový, že L(G) = L(1Z).
Důkaz. Vrchol zásobníku píšeme vpravo.
Konstruujeme rozšířený PDA 1Z, který simuluje pravou derivaci v Q v obráceném pořadí.
PDA 1Z má kroky dvojího typu:
□ může kdykoli načíst do zásobníku symbol ze vstupu
H (redukce) je-li na vrcholu zásobníku řetězec tvořící pravou stranu nějakého pravidla v g, může ho nahradit odpovídajícím levostranným neterminálem (a ze vstupu nic nečte)
IB102 Automaty a gramatiky, 2.12.2019
15/19
Nechť Q = (A/, Z, P, S).
Položme 7£ = ({q, r}, Z, A/u Z u {_l},5, q, _l, {r}), kde _l je nově přidaný symbol a kde 8 je definována takto:
D 8(q, a, e) = {(q, a)} pro všechna a g Z
B je-li A^ř a pravidlo v P, pak 8(q, e, a) obsahuje (q, /4)
Q (S(q,e,±S) = {(r,e)}
IB102 Automaty a gramatiky, 2.12.2019
16/19
krok výpočtu       odpovídající pravidlo z Q
{q, / + /* /, _L) f			-L0	F ^ i
F	(q,			T ^ F
F	(q,		-L 71	E-f T
F	(q,			
	(<7>		-L*+)	
	(q,	*/,	J-E + /)	F ^ i
		*/,	±E + F)	T ^ F
		*/,	±E+T)	
F		/,	±E+ T*)	
		e,	±E+T* /')	F ^ i
F		e,	±E+T*F)	r   r * f
F	(Q,	e,	±E+T)	E^ E+T
F	(q,	e,		
F		e,	e)	
IB102 Automaty a gramatiky, 2.12.2019
Korektnost
aAyAxy (q,xy,±)[^-(q,y,±aA)
n
kde S =4>* aAy =4> xy je pravá derivace a A je nejpravější neterminál
(=4>) indukcí k délce odvození (<==) indukcí k délce výpočtu
Pro A = S aa,y = e dostáváme:
x ^ (q,x,±)\^(q,e,±S)
"Výstupem" je pravá derivace v obráceném pořadí.
IB102 Automaty a gramatiky, 2.12.2019
Efektivnost syntaktické analýzy
Nederministický PDA =4> nedeterministický algoritmus =4> exponenciální deterministický algoritmus
Řešení:
deterministický algoritmus složitosti 0(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 a gramatiky, 2.12.2019
19/19