Zásobníkové automaty a bezkontextové jazyky
r
rozšírene
PDA
Lemma 3.45
triviaine
PDA
akceptující koncovým štavem
Veta 3.39
Veta 3.39
PDA
akceptující prazdným zašobn íkem
r
CFG
IB102 Automatý a gramatiký, 29. 11. 2010
1
Zásobníkové automaty a bezkontextové jazyky
Motivace 1: Jaka je trída jazyků  rozpoznávaných zásobníkovými automaty?
Motivace 2: Je dana bezkontextova gramatika G a slovo w. Jak zjistit, zda slovo w sa da vygenerovat v gramatice G?
Problém syntaktické analýzy pro bezkontextové gramatiky:
pro danou bezkontextovou gramatiku G a slovo w rozhodnout, zda w G L(G)■
IB102 Automaty a gramatiky, 29.11.2010
2
Ekvivalence bezkontextových gramatik a zásobníkových automatů
Veta 3.51. Ke každému PDA M lze sestrojit CFG G takovou, že Le(M) = L(G).
Důkaz. Vynechán. □
Veta 3.47. Ke každe CFG G lze sestrojit PDA M takovy, že L(G )= Le(M).
Důkaz. Uvedeme za chvíli. □
Důsledek 3.52. Trída jazyku rozpoznavanych zasobníkovymi automaty je prave trída bezkontextovych jazykU.
IB102 Automaty a gramatiky, 29.11.2010
3
Intuice převodu PDA na CFG
1. |Q| = 1
IB102 Automaty a gramatiky, 29.11.2010
4
Intuice převodu PDA na CFG
2. |Q| > 2
IB102 Automaty a gramatiky, 29.11.2010
5
Intuice převodu CFG na PDA
Konstrukce PDA řeší problém syntaktické analýzy. (platí pro dané G a w: w G L(G)?)
w G L (G) <^=^ v G existuje derivaCní strom s výsledkem w
IB102 Automaty a gramatiky, 29.11.2010
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 nahorů
IB102 Automaty a gramatiky, 29.11.2010
7
Intuice pro analýzu shora dolů
Budován í derivacn ího stromu simuluje levé derivace, tj. vždy rozv íj íme nejlevejs í neterminál.
IB102 Automaty a gramatiky, 29.11.2010
8
Nedeteřministicka syntakticka analýza shořa dolU
Veta 3.47.     Ke kaZde CFG G lze sestrojit PDA M takovy, Ze
L(G ) = Le(M).
DUkaz. K dane gramatice G konstruujeme PDA M, ktery simůlůje leve derivace v G.
• V leve derivaci je v jednom kroků odvození nahrazen (nejlevejsí) neterminal A pravoů stranou X1.. .Xn nejakeho A-pravidla.
• V M teto situaci odpovída nahrada A na vrcholů zasobníků retezem
X1 . . . Xn.
M = ({q}, S, N U S, 5, q, S, 0), kde 5 je definovala:
• 5(q, e, A) obsahuje (q, a) prave kdyz A —» a G P
• 5(q, a, a) = {(q, e)} pro vsechna a G S
IB102 Aůtomaty a gramatiky, 29. 11. 2010
9
S(q, e, S) = {(q, aAB)} S(q, e, A) = {(q, Aa), (q, e)}
S(q,e,B) = {(q,SaA), (q, b)}
S(q, a, a) = S(q, b, b) = {(q, e)}
S == aAB == aB == aSaA == aaABaA == aaBaA = aabaA = aaba
S — aAB A — Aa j e B — SaA j b
IB102 Automaty a gramatiky, 29.11.2010
10
Korektnost
A =^>* w (q,w,Ä) \^—(q,e,é)
(=>) Indukcí vzhledem k délce odvození m.
1. m = 1: zrejme.
2. m > 1: necht tvrzení platí pro všechna m' < m.
A =4 XiX2 ... Xk =4* x\x2 ... xk = w, kde Xi =4 xi, 0 < mi < m z definice ô plyne (g, w, A) |— (g,    X1X2 ... Xk).
Je-li Xi G N, pak dle indukcn ího predpokladu mame
(q,Xi,Xi)
Je-li G S, pak = x^ a z definice 5 plyne (g, x^, x^) |— (g, £, č). Kompozicí dostávame (q,w,A) \-^—(q,£,s).
IB102 Automaty a gramatiky, 29. 11. 2010
11
(<=) Předpokládejme (q,w,Á) p-(#, £, e) a ukažme A =^>+ w. Indukcí vzhledem k delce vypoCtu n.
1. n = 1: zrejme.
2. n > 1: necht tvrzení platí pro vsechna n' < n.
(q,w,A) \—(q,w,X1X2...Xk), tj. A     XľX2 ... Xk G P
w muzeme napsat jako w = xix2 .. .xk takove, ze
• je-li Xi G N, pak (q,Xi,Xi) p*-s), kde rti < n. Dle IP Xi ^+ xi.
• je-li Xi G T, pak Xi 4> xi. Vhodnou kompozicí obdrzíme
A     XiX2 ... Xk      xiX2 ... Xk =^>* xi... xk = w
coz je leva derivace slova w v gramatice G. □
IB102 Automaty a gramatiky, 29. 11. 2010
12
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 29.11.2010
13
Intuice pro analýzu zdola nahoru
IB102 Automaty a gramatiky, 29.11.2010
14
Nedeterministická syntaktická analýza zdola nahoru
Věta 3.55. Necht G je libovolná CFG, pak lze zkonstruovat rozs írený PDA R takový, Ze L(G) = L (R).
DUkaz. Vrchol zasobníku píSeme vpravo.
Konstruujeme rozs írený PDA R, který simuluje pravou derivaci v G v obracenem porad í.
PDA R ma kroký dvoj ího týpu:
1. muze kdýkoli C íst do zasobn íku vstupn ísýmbol,
2. (redukce) je-li na vrcholu zasobn íku retez tvoríc í pravou stranu nejakeho pravidla v G, muze ho nahradit odpov ídaj íc ím levostranným neterminalem (a ze vstupu nic necte).
IB102 Automatý a gramatiký, 29.11.2010
15
Necht G = (N, S, P, S).
Polozme R = ({q, r}, S, N U S U{±},5,q, _L, {r}), kde JL je nove pridany symbol a kde 5 je definovana takto:
1. 5(q, a, e) = {(q, a)} pro vsechna a G S,
2. je-li A — a, pak 5(q, e, a) obsahuje (q, A),
3. 5(q, e, ±S) = {(r, e)}.
IB102 Automaty a gramatiky, 29.11.2010
16
krok vypoCtu
odpov ídaj íc í pravidlo z G
(q, i + i * i, _L)
i		* i, L i)	F — i
£	■ (q +i	* i, LF)	T — F
£		* i, LT)	E — T
£	(q, +i * i, L_E)		
+	- (q,   i * i, L_E+)		
i	(q,	*i, LlE + i)	F - i
£	(q,	*i, LE + F)	T — F
£	(q,	*i, LE + T)	
*	(q,	i, LE + T*)	
i	(q,	e, LE + T * i)	F — i
£	(q,	e, LE + T * F)	T—T
£	(q,	e, LE + T)	e — e
£	(q,	e, LE)	
£	■(r,	e, e)	
Korektnost
S =^>* aAy =5> xy (g, xy, _L) p1- (g, y, _LceA),
kde S      aAy =5> xy je prava derivace a A je nejpravější neterminal
(=>) indukcí k delce odvození (^=) indukcí k delce výpoCtu
Pro A = S a a, y = e dostavame:
S =^>* x (g, x, _L) p-(g,   -LaS) I—(r, e)
"Výstupem" je prava derivace v obracenem poradí. □
IB102 Automaty a gramatiky, 29.11.2010
18
Efektivnost syntaktické analyzy
Nederministicky PDA       nedeterministicky algoritmus =>* exponencialn í deterministicky algoritmus
ReSení:
• deterministicky algoritmus slozitosti O (n3), kde n = |w (algoritmus Cocke - Younger - Kasami)
• deterministicke zasobn íkove automaty a deterministicke bezkontextove jazyky
• linearn í algoritmy pro specialn í trídy deterministickych bezkontextovych jazyku
IB102 Automaty a gramatiky, 29. 11. 2010
19