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 a gramatiky, 27.11.2017
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, 27.11.2017
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, 27.11.2017
3/19
Intuice převodu PDA na CFG
1.0=1
IB102 Automaty a gramatiky, 27.11.2017
4/19
Intuice převodu PDA na CFG
2. O > 2
IB102 Automaty a gramatiky, 27.11.2017
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, 27.11.2017
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, 27.11.2017
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, 27.11.2017
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, 27.11.2017
9/19
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 a gramatiky, 27.11.2017
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 ... 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 a gramatiky, 27.11.2017
11/19
(<==) 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 a gramatiky, 27.11.2017
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 27.11.2017
13/19
Intuice pro analýzu zdola nahoru
S XY
X ->• ab
Y ->• c
IB102 Automaty a gramatiky, 27.11.2017
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, 27.11.2017
15/19
Nechť G = (N, e, P, s).
Položme 72. = ({q, r}, z, A/ u e U {_L}, 5, q, _L, {r}), kde ± je nově přidaný symbol a kde S je definována takto:
D 5(q, a, e) = {(q, a)} pro všechna a e Y.
Q je-li A -> a pravidlo v P, pak S(q, e, a) obsahuje (q, A)
m S(q,s,±S) = {(r,e)}
IB102 Automaty a gramatiky, 27.11.2017
16/19
krok výpočtu       odpovídající pravidlo z Q
{q, / + /* /, _L) f	(<7>		-L0	F ^ i
F	(q,			T ^ F
F	(q,		-L 71	E-f T
	(q,			
	(<7>		-L*+)	
	(<7>	*/,	J-e + /)	F ^ i
F	(<7>	*/,	±E + F)	T ^ F
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, 27.11.2017
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, 27.11.2017
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, 27.11.2017
19/19