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, 28.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 Ql
Problém syntaktické analýzy pro bezkontextové gramatiky:
pro danou bezkontextovou gramatiku Q a slovo w rozhodnout,
zda w £ L(Q).
IB102 Automaty a gramatiky, 28.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{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 28.11. 2011
3
Intuice převodu PDA na CFG
1. Q = 1
IB102 Automaty a gramatiky, 28.11. 2011
4
Intuice převodu PDA na CFG
2. Q >2
IB102 Automaty a gramatiky, 28.11. 2011
5
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 a gramatiky, 28.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, 28.11. 2011
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, 28.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 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 a gramatiky, 28.11. 2011
9
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 a gramatiky, 28.11.2011
10
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 Sř pak Xi = 2^ a z definice 5 plyne (g, a^, 2^) |— (g, £, e)
Kompozicí dostáváme (g, £, £)■
IB102 Automaty a gramatiky, 28.11. 2011
11
(<=) 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 ...      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 Xi ^+
je-li Xi G S, pak Xi 4> 2^
Vhodnou kompozicí obdržíme
A =^> ... Xk      ^1^2 • • • Xk      xi.. .Xk = w
což je levá derivace slova w v gramatice C/. □
IB102 Automaty a gramatiky, 28.11. 2011
12
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 28.11. 2011
13
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 28.11. 2011
14
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 a gramatiky, 28.11. 2011
15
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 a gramatiky, 28.11. 2011
16
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 a gramatiky, 28.11. 2011
18
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 a gramatiky 28.11. 2011
19