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 a gramatiky, 26.11.2011
1
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 Q?
Problém syntaktické analýzy pro bezkontextové gramatiky:
pro danou bez kontextovo u gramatiku Q a slovo w rozhodnout,
zda w G L(Q).
IB102 Automaty a gramatiky, 26.11.2011
2
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(g) = 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, 26.11.2011
3
Intuice převodu PDA na CFG
1. \Q\ = 1
IB102 Automaty a gramatiky, 26.11.2011
4
Intuice převodu PDA na CFG
2. \Q\ > 2
IB102 Automaty a gramatiky, 26.11.2011
5
Intuice převodu CFG na PDA
Konstrukce PDA řeší problém syntaktické analýzy, (platí pro dané Q a w: w G L{Q)1)
w G L(Q) v Q existuje derivační strom s výsledkem w
IB102 Automaty a gramatiky, 26.11. 2011
6
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, 26.11.2011
7
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, 26.11.2011
8
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 Ai, 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}, Ti, N U Ti, ô, q, S, 0), kde ô je definována:
• 5(q,e,A) obsahuje (q, a) právě když A     a G P
• 5(q,a,a) = {(q, s)} pro všechna a G E
IB102 Automaty a gramatiky, 26.11.2011
9
S aAB A ->■ Aa I e ß      SaA I 6
S(q,e,A) S(q,e,B) 8{q, a, a)
{(q,aAB)} {(q,Aa),{q,s)}
{(q,SaA),(q,b)} S(q,b,b) = {(q,e)}
S
aAB
aB
aSaA
aaABaA
aaBaA
aabaA
aaba
IB102 Automaty a gramatiky, 26.11.2011
10
Korektnost
A =4>* w (g, w,A) p-(g, £,£)
(=>) Indukcí vzhledem k délce odvozením.
1. m = 1: zřejmé.
2. m > 1: necht tvrzení platí pro všechna m' < m.
A =>► X1X2 ... Xk X1X2 ... Xk = w, kde Xi ^ Xi, 0 < rrii < m z definice 5 plyne (g, w, A) |— (g,    X1X2 ... Xk).
Je-li     G TV, pak dle indukčního předpokladu máme
(q,Xi,Xi) P^(g,s,s).
Je-li Xi G E, pak 1^ = a z definice 5 plyne (g, aľi, |— (g, £, s). Kompozicí dostáváme (q,w,A) |-^(g,£, £)■
IB102 Automaty a gramatiky, 26.11. 2011 11
(<=) Předpokládejme (q,w,Á) p-(5,£,£) 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.
\—(q,w,X1X2...Xk), tj. A^XiX2...Xfc G P
w můžeme napsat jako w = X1X2 ...     takové, že
• je-li     G AT, pak (q,Xi,Xi) p*-(?,£,£)» kde n* < n-Dle IP
• je-li Xi G S, pak     4> 2^. Vhodnou kompozicí obdržíme
A =>► X1X2 ... Xk      ^1X2 ... Xk      xi.. .Xk = w
což je levá derivace slova w v gramatice č/. □
IB102 Automaty a gramatiky, 26.11.2011
12
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 26.11.2011
13
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 26.11.2011
14
Nedeterministická syntaktická analýza zdola nahom
Věta 3.55. Necht Q je libovolná CFG, pak lze zkonstruovat rozšírený PDA U takový, že L {Q) = L(K).
Důkaz. Vrchol zásobníku píšeme vpravo.
Konstruujeme rozšírený PDA 71, který simuluje pravou derivaci v Q v obráceném poradí.
PDA 7Z 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 a gramatiky, 26.11.2011
15
Necht g = (TV, E, P, S).
Položme K = ({q, r}, E, TV U E U {_L}, ô, q, _L, {r}), kde _L je nově přidaný symbol a kde ô je definována takto:
1. a, s) = {(g, a)} pro všechna a G E,
2. je—Ii A —>> a, pak      e, a) obsahuje (g, A),
3. í(g,e,±S) = {(r,e)}.
IB102 Automaty a gramatiky, 26.11.2011
16
krok výpočtu odpovídající pravidlo z Q
(q, i + i * z, _L)	i	(q, +i	* i,	-L0	F ->• i
	e	■ (g, +«	* i,	±F)	T —)• F
	e	• (g,	* i,	XT)	£ľ —> T
	e	(g,	* i,	±E)	
	+	- (g,   i * i,		±E+)	
	i	(g,	*i,	-LE + i)	F ->• i
	e	(g,	*i,	\ E + F)	T -> F
	e	(g>		1 E + T)	
	*	-(g,	• z,	\ E + T*)	
	i	(g,	s,	1 ft + T*i)	F -»■ i
	e	(g,	s,	1 E + T* F)	T —>• T * i*1
	e	-(g,	s,	\ E + T)	E ^ E + T
	e	(g,	s,	1 fi)	
	£	-(r>	s,	e)	
Korektnost
S      otAy     xy (g, xy, _L)      (g, ±aA),
kde S      a-Ay 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 b a,y = e dostáváme:
S^* x
(r, e)
Výstupem" je pravá derivace v obráceném pořadí.
□
IB102 Automaty a gramatiky, 26.11.2011
18
Efektivnost syntaktické analýzy
Nederministický PDA =>► nedeterministický algoritmus ==> 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é bez kontextové jazyky
• lineární algoritmy pro speciální třídy deterministických bez kontextových jazyků
IB102 Automaty a gramatiky, 26.11.2011
19