Greibachové normální forma Definice 3.33. Bezkontextová gramatika Q = (TV, S,P, S) je v Greibachové normální formě (GNF) právě když • Q je bez ^-pravidel a • každé pravidlo z P je tvaru A —> a<% kde a £ S a ce £ N* (s případnou výjimkou pravidla S —» e). Věta 3.34. Každý bez kontextový jazyk lze generovat bez kontextovo u gramatikou v Greibachové normální formě. IB102 Automaty a gramatiky, 23.11.2009 1 Motivační příklad A B BB bBa aAa bAb IB102 Automaty a gramatiky, 23.11.2009 2 Lemma o substituci (pro připomenutí) Lemma 3.20. (o substituci) Necht g = (N, E, P, S) je CFG. Necht A -► aľBa2 G P. Necht B —»/?i I ... I ßr jsou všechna pravidla v P tvaru B a, Definujme Q' = (N, E, P7, 5), kde P' = (P \ {A -> aiBa2}) U {A -> ai/?ia2 cei/3rce2} Pak £(£) = £(£')■ IB102 Automaty a gramatiky, 23.11.2009 3 Rekursivní neterminály a gramatiky Definice 3.28. Neterminál A v CFG Q = (TV, S,P, S) se nazývá levorekursivní jestliže v Q existuje derivace A =^>+ Aß. CFG bez levorekursivních neterminálů se nazývá nelevorekursivní. Převod bezkontextové gramatiky Q do GNF: L(Q) je prázdný: zřejmé (S —» a5) L(^) je neprázdný: 1. z vlastní gramatiky eliminujeme levou rekurzi 2. pak převedeme do GNF IB102 Automaty a gramatiky, 23.11.2009 4 Algoritmus odstranění přímé levé rekurze Necht Q = (TV, S, P, S) je bezkontextová gramatika, v níž všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru A -> Aai Aam ßi ß- ni kde každý řetěz ßi začíná symbolem různým od A. Necht Q' = (N U {A'}, E, P', S), kde P7 obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly A^ß! ßn ßlÄ ßnÄ A' a\ a m «i A' amÄ Pak £(£) = £(£')■ IB102 Automaty a gramatiky, 23.11.2009 5 Příklad A - -> Bd c B - -> Bdd Ccc C - ^ Aa aAd IB102 Automaty a gramatiky, 23.11.2009 6 Algoritmus odstranění levé rekurze Vstup: Vlastní CFG Q = (TV, E, P, 5) Výstup: Ekvivalentní nelevorekursivní gramatika i Uspořádej libovolně N, N = {Ai,..., An} 2 for i <— 1 to n do 3 4 5 6 7 8 9 io od for j <— 1 to i — 1 do foreach pravidlo tvaru Ai —» A7-a do přidej pravidla A^ —»/?ia Ä a (kde A- -> /3i /3fe jsou všechna yL-pravidla) výpust pravidlo Ai —» Am od od odstraň případnou přímou levou rekurzi na Ai IB102 Automaty a gramatiky, 23.11.2009 7 Korektnost algoritmu Konečnost. Ekvivalence gramatik: Všechny úpravy jsou dle Lemmatu o substituci nebo odstraňují přímou levou rekurzi. Výsledná gramatika je nelevorekursivní: 1. po i-té iteraci vnějšího cyklu začíná každé A^-pravidlo bud terminálem nebo neterminálem A^, kde k > i. 2. po j-té iteraci vnitřního cyklu začíná každé A^-pravidlo bud terminálem nebo neterminálem Aj^ kde k > j. IB102 Automaty a gramatiky, 23.11.2009 8 Příklad A B C D E Ba CC aE CDa bb Db c Eb IB102 Automaty a gramatiky, 23.11.2009 9 Algoritmus transformace do GNF Vstup: Nelevorekursivní CFG Q = (TV, S, P, S) bez ^-pravidel Výstup: CFG Q' v GNF splňující L{Q) = L(Qf) i najdi lineární uspořádání -<< splňující (A —» Ba) £ P => 2 Označme N = {Ai,..., An \ Ai_i -< A^ 1 < i < n} 3 for i <— n — 1 downto 1 do foreach pravidlo tvaru Ai —> A ja, kde j > i 4 5 6 7 8 9 od přidej pravidlo Ai (kde Aj -> ßi výpust pravidlo A, ß\OL ßkOi ßk jsou všechna yL-pravidla) A ja od io náhrad potřebné terminály novými neterminaly n a přidej příslušná pravidla A^B IB102 Automaty a gramatiky, 23.11.2009 10 55 55 Korektnost algoritmu Konečnost. Ekvivalence gramatik. Výsledná gramatika je v GNF. IB102 Automaty a gramatiky, 23.11.2009 11 Zásobníkové automaty IB102 Automaty a gramatiky, 23.11.2009 12 Definice zásobníkového automatu Definice 3.36. Nedeterministický zásobníkový automat (PushDown Automaton, PDA) je sedmice M = (Q, S, T, 5, g0? ^o? F), kde • Q je konečná množina, jejíž prvky nazýváme stavy, • S je konečná množina, tzv. vstupní abeceda, • T je konečná množina, tzv. zásobníková abeceda, • 5 : Q x (S U {e}) xT^ Vfíu(Q x r*), tzv. (parciální) přechodová funkce1, • Qo £ Q je počáteční stav, • Zo G T je počáteční symbol v zásobníku, • F C Q je množina koncových stavů. ^ápis VfíuÍQ x T*) značí množinu všech konečných podmnožin množiny Q x T*. IB102 Automaty a gramatiky, 23.11. 2009 13 Výpočet zásobníkového automatu Definice 3.37. Necht M = (Q, E, r, ô, q0, Z0, F) je PDA. Konfigurací nazveme libovolný prvek (p,w,a) G Q x S* x T * Na množině všech konfigurací automatu A4 definujeme binární relaci krok výpočtu M takto (p,aw, Za) ,def M (g, w, 7«) <^^> 3(g, 7) G 5(p, a, Z) pro a G S U {č} Reflexivní a tranzitivní uzávěr relace M značíme * Je-li A4 zřejmý z kontextu, píšeme pouze I— resp M * IBIO2 Automaty a gramatiky, 23.11.2009 14 Akceptující výpočet zásobníkového automatu Definice 3.37.(pokračování) Jazyk akceptovaný PDA A4 koncovým stavem definujeme jako L(M) = {w G S* I (go, w, Zo) p- (