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 IB102 Automaty a gramatiky, 7.12.2009 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 bez kontextovo u gramatiku Q a slovo w rozhodnout, zda w G L{Q). IB102 Automaty a gramatiky, 7.12.2009 2 Ekvivalence bezkontextových gramatik a zásobníkových automatů Věta 3.51. Ke každému PDA A4 lze sestrojit CFG Q takovou, že Le(M)=L(g). Důkaz. Vynechán. D 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, 7.12.2009 3 Intuice převodu PDA na CFG 1. \Q\ = l IB102 Automaty a gramatiky, 7.12.2009 4 Intuice převodu PDA na CFG 2. \Q\ >2 IB102 Automaty a gramatiky, 7.12.2009 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, 7.12.2009 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, 7.12.2009 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, 7.12.2009 8 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 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 A4 této situaci odpovídá náhrada A na vrcholu zásobníku řetězem Xi... Xn. M = ({g}, S, TV U S, 5, g, S, 0), kde 5 je definována: • 8(q,e,A) obsahuje (q, a) právě když A —» a G P • ö(q,a,a) = {((?,£)} pro všechna a G S IB102 Automaty a gramatiky, 7.12.2009 9 ô(q,e, S) = {(q,aAB)} S(q,e,A) = {(q,Aa),(q,e)} S(q,e,B) = {(q, S a A), (q, b)} ô(q,a,a) = ô(q,b,b) = {(q, e)} S => aAB =4> aB => aSaA => aaABaA => aaBaA => aabaA =$■ aaba S A B aAB Aa e SaA b IB102 Automaty a gramatiky, 7.12.2009 Korektnost A (^=>) Indukcí vzhledem k délce odvozením. 1. mn = l\ zřejmé. 2. m > 1: necht tvrzení platí pro všechna m7 < m. ra* A =>* X1X2 ... Xfc =^>* X1X2 ... x/e = ^, kde Xi '=¥ Xi, 0 < mi < m z definice 5 plyne (g, w, A) |— (g, w, X\X^ ... -X&). Je-li X^ G X, pak dle indukčního předpokladu máme Je-li I^gS, pak Xi = x^ a z definice 5 plyne (g, x^, x i) |— (g, £, e) + Kompozicí dostáváme (g,^,A) |—(q,e,e). IBIO2 Automaty a gramatiky, 7.12.2009 11 (<=) Předpokládejme (q,w,A) p-(#, £, 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 rť < n. (g,w,A) |—(g,w,XiX2...Xfe), tj. A^X!X2...Xfc e P w můžeme napsat jako w = #1X2 • • • xk takové, že • je—li Xi G N, pak (q,Xi,Xi) p*-( x^ Vhodnou kompozicí obdržíme A => X1X2 ... Xk =^* X1X2 ... Xk =^* xi.. .Xk = w což je levá derivace slova w v gramatice Q. D IBIO2 Automaty a gramatiky, 7.12.2009 12 Intuice pro analýzu zdola nahoru IB102 Automaty a gramatiky, 7.12.2009 13 Intuice pro analýzu zdola nahoru IB102 Automaty a gramatiky, 7.12.2009 14 Nedeterministická syntaktická analýza zdola nahom Věta 3.55. Necht Q je libovolná CFG, pak lze zkonstruovat rozšířený PDA TI takový, že L {Q) = L{K). Důkaz. Vrchol zásobníku píšeme vpravo. Konstruujeme rozšířený PDA TZ, který simuluje pravou derivaci v Q v obráceném pořadí. PDA TZ 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, 7.12.2009 15 Necht g = (N, E, P, S). Položme TI = ({g, r}, S, TV U S U {±},5,g,_L,{r}), kde _L je nově přidaný symbol a kde 5 je definována takto: 1. S(q,a,e) = {(g, a)} pro všechna a G S, 2. je-li A —» a, pak 5(g, £, a) obsahuje (g, A), 3. %,e,±5) = {(r,e)}. IB102 Automaty a gramatiky, 7.12.2009 16 (g, i + i*i, _L) krok výpočtu (g, +i * i (g, +i * i (g, +i * i (g, +i * i -(g, i * i. + * (í' (í' (í' (r, *i. *i. i. e. e. e. e. e. -Li) _LF) LT) LE) LE+) LE + i) LE + F) LE + T) LE + T*) LE + T* i) LE + T* F) LE + T) LE) e) odpovídající pravidlo z Q F ->i T F F ->i T ^T*F E^E + T Korektnost S =^>* aAy => xy «<=>* (g, xy, _L) P~ (g, ?/, _LceA) kde S =^>* ceA?/ => 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 ot^y — e dostáváme: S * x z_____\ < > N 7 {q,x,.L) ^-(q,e,±S) (r,e) "Výstupem" je pravá derivace v obráceném pořadí. D IB102 Automaty a gramatiky, 7.12.2009 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é bez kontextové jazyky • lineární algoritmy pro speciální třídy deterministických bez kontextových jazyků IB102 Automaty a gramatiky, 7.12.2009 Vlastnosti bezkontextových jazyků Věta 3.58. (a 3.61.) Třída bezkontextových jazyků (£2) je uzavřena vzhledem k operacím 1. sjednocení 2. zřetězení 3. iterace 4. pozitivní iterace 5. průnik s regulárním jazykem Věta 3.60. Třída bezkontextových jazyků (£2) Ví^Víl uzavřena vzhledem k operacím 1. průnik 2. doplněk IBIO2 Automaty a gramatiky, 7.12.2009 20 Sjednocení Li je generován CFG Q\ = (TVi, Ei, Pi, S\) a L2 je generován CFG Q2 = (iV2, £2, P2, S2) Bez újmy na obecnosti můžeme předpokládat JVi íl ÍV2 = 0. Definujeme g = (N1UN2U {S}, £1 U E2, P, 5), kde 5 je nový symbol a P = p1 u P2 U {S -► 5i, 5 -► S2} Každá derivace v C? začne použitím bud S —» £1 nebo 5 —» 52. Podmínka iVi n JV2 = (3 zaručí, že při použití S —> £1 (resp. 5 —> £2) lze v dalším derivování používat jen pravidla z P± (resp. P2). Jazyk L = Li U L2 je generován gramatikou Q. IBIO2 Automaty a gramatiky, 7.12.2009 21 Zřetězení Li je generován CFG Q\ = (TVi, Ei, Pi, S\) a L2 je generován CFG Q2 = (iV2, S2, P2, #2) Bez újmy na obecnosti můžeme předpokládat JVi íl ÍV2 = 0. Definujeme g = (N1UN2U {S}, Si U S2, P, 5), kde 5 je je nový symbol a P = Pi U P2 U {S -► S^} Jazyk L = L\.L2 je generován gramatikou C/. IBIO2 Automaty a gramatiky, 7.12.2009 Iterace a pozitivní iterace Li je generován CFG Q\ = (7Vi, Si, Pí, S\) Definujeme Q = (N\ U {S}, Si, P, 5), kde 5 je je nový symbol a P = Pi U {S-► SSí | e} Jazyk L = LI je generován gramatikou £?. Definujeme Q = (TVi U {S}, Si, P, 5), kde S je je nový symbol a P = Pi U {S-► SSí | Si} _ r + Jazyk L = L^ je generován gramatikou Q IB102 Automaty a gramatiky, 7.12. 2009 23 Korektnost konstrukce pro iteraci Dokážeme L(Q) = L\. IB102 Automaty a gramatiky, 7.12.2009 24 Průnik a doplněk Lľ = {anbncm I m,n > 1} L2 = {ambncm | m,n > 1} Oba tyto jazyky jsou CFL. Kbyby £2 byla uzavřena vzhledem k operaci průniku, pak i Li n L2 {anbncn I n > 1} musel být bez kontextový, což však není. Neuzavřenost £2 vůči doplňku plyne z její uzavřenosti na sjednocení, neuzavřenosti na průnik a z De Morganových pravidel: Li n L2 = co-(co-Li U C0-L2), tj., kdyby £2 byla uzavřena na doplněk, musela by být uzavřena i na průnik, což však není. IBIO2 Automaty a gramatiky, 7.12.2009 25 Průnik s regulárním jazykem L = L(V), kdePjePDAP = (g1,S,r,«51,g1,Z0,F1) R = L(A), kde A je deterministický FA A = (Q2, S, 62, q2, -^2) Sestrojíme PDA V takový, že L{V')=L n R. V' = {Q,Y.,T,ô,qQ,ZQ,F), kde • Q = Qi x Q2, • qo = (?i,í2> • F = Fi x F2 • í : pro každé p £ Qi, q £ Q2, aeSU {e}, Z