Zásobníkové automaty a bezkontextové jazyky 76 54 01 23 rozšířené PDA Lemma 3.45 // 76 54 01 23 PDA akceptující koncovým stavem triviálně oo Věta 3.39 // 76 54 01 23 PDA akceptující prázdným zásobníkem Věta 3.39 oo 76 54 01 23 CFG IB102 Automaty a gramatiky, 1. 12. 2008 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 G a slovo w. Jak zjistit, zda slovo w sa dá vygenerovat v gramatice G? Problém syntaktické analýzy pro bezkontextové gramatiky: pro danou bezkontextovou gramatiku G a slovo w rozhodnout, zda w L(G). IB102 Automaty a gramatiky, 1. 12. 2008 2 Ekvivalence bezkontextových gramatik a zásobníkových automatů Věta 3.51. Ke každému PDA M lze sestrojit CFG G takovou, že Le(M) = L(G). Důkaz. Vynechán. 2 Věta 3.47. Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M). Důkaz. Uvedeme za chvíli. 2 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, 1. 12. 2008 3 Intuice převodu PDA na CFG 1. |Q| = 1 IB102 Automaty a gramatiky, 1. 12. 2008 4 Intuice převodu PDA na CFG 2. |Q| 2 IB102 Automaty a gramatiky, 1. 12. 2008 5 Intuice převodu CFG na PDA Konstrukce PDA řeší problém syntaktické analýzy. (platí pro dané G a w: w L(G)?) w L(G) v G existuje derivační strom s výsledkem w IB102 Automaty a gramatiky, 1. 12. 2008 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, 1. 12. 2008 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, 1. 12. 2008 8 Nedeterministická syntaktická analýza shora dolů Věta 3.47. Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M). Důkaz. K dané gramatice G 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. * V M této situaci odpovídá náhrada A na vrcholu zásobníku řetězem X1 . . . Xn. M = ({q}, , N , , q, S, ), kde je definována: * (q, , A) obsahuje (q, ) právě když A P * (q, a, a) = {(q, )} pro všechna a IB102 Automaty a gramatiky, 1. 12. 2008 9 S aAB (q, , S) = {(q, aAB)} A Aa | (q, , A) = {(q, Aa), (q, )} B SaA | b (q, , B) = {(q, SaA), (q, b)} (q, a, a) = (q, b, b) = {(q, )} S aAB aB aSaA aaABaA aaBaA aabaA aaba IB102 Automaty a gramatiky, 1. 12. 2008 10 Korektnost A w (q, w, A) | (q, , ) (=) Indukcí vzhledem k délce odvození m. 1. m = 1: zřejmé. 2. m > 1: nechť tvrzení platí pro všechna m < m. A X1X2 . . . Xk x1x2 . . . xk = w, kde Xi mi xi, 0 mi < m z definice plyne (q, w, A) | (q, w, X1X2 . . . Xk). Je-li Xi N, pak dle indukčního předpokladu máme (q, xi, Xi) | (q, , ). Je-li Xi , pak Xi = xi a z definice plyne (q, xi, xi) | (q, , ). Kompozicí dostáváme (q, w, A) | + (q, , ). IB102 Automaty a gramatiky, 1. 12. 2008 11 (=) Předpokládejme (q, w, A) | n (q, , ) a ukažme A + w. Indukcí vzhledem k délce výpočtu n. 1. n = 1: zřejmé. 2. n > 1: nechť tvrzení platí pro všechna n < n. (q, w, A) | (q, w, X1X2 . . . Xk), tj. A X1X2 . . . Xk P w můžeme napsat jako w = x1x2 . . . xk takové, že * je-li Xi N, pak (q, xi, Xi) | ni (q, , ), kde ni < n. Dle IP Xi + xi. * je-li Xi , pak Xi 0 xi. Vhodnou kompozicí obdržíme A X1X2 . . . Xk x1X2 . . . Xk x1 . . . xk = w což je levá derivace slova w v gramatice G. 2 IB102 Automaty a gramatiky, 1. 12. 2008 12 Intuice pro analýzu zdola nahoru IB102 Automaty a gramatiky, 1. 12. 2008 13 Intuice pro analýzu zdola nahoru IB102 Automaty a gramatiky, 1. 12. 2008 14 Nedeterministická syntaktická analýza zdola nahoru Věta 3.55. Nechť G je libovolná CFG, pak lze zkonstruovat rozšířený PDA R takový, že L(G) = L(R). Důkaz. Vrchol zásobníku píšeme vpravo. Konstruujeme rozšířený PDA R, který simuluje pravou derivaci v G v obráceném pořadí. PDA R 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 G, může ho nahradit odpovídajícím levostranným neterminálem (a ze vstupu nic nečte). IB102 Automaty a gramatiky, 1. 12. 2008 15 Nechť G = (N, , P, S). Položme R = ({q, r}, , N {}, , q, , {r}), kde je nově přidaný symbol a kde je definována takto: 1. (q, a, ) = {(q, a)} pro všechna a , 2. je-li A , pak (q, , ) obsahuje (q, A), 3. (q, , S) = {(r, )}. IB102 Automaty a gramatiky, 1. 12. 2008 16 krok výpočtu odpovídající pravidlo z G (q, i + i i, ) | i (q, +i i, i) F i | (q, +i i, F) T F | (q, +i i, T) E T | (q, +i i, E) | + (q, i i, E+) | i (q, i, E + i) F i | (q, i, E + F) T F | (q, i, E + T) | (q, i, E + T) | i (q, , E + T i) F i | (q, , E + T F) T T F | (q, , E + T) E E + T | (q, , E) | (r, , ) Korektnost S Ay n xy (q, xy, ) | (q, y, A), kde S Ay n 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 , y = dostáváme: S x (q, x, ) | (q, , S) | (r, ) "Výstupem" je pravá derivace v obráceném pořadí. 2 IB102 Automaty a gramatiky, 1. 12. 2008 18 Efektivnost syntaktické analýzy Nederministický PDA = nedeterministický algoritmus = exponenciální deterministický algoritmus Řešení: * deterministický algoritmus složitosti O(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, 1. 12. 2008 19