^-pravidla Definice 3.13. Řekneme, že CFG Q = (TV, S,P, S) je bez ^-pravidel právě když bud 1. P neobsahuje žádné ^-pravidlo (tj. pravidlo tvaru A —» e ) nebo 2. v P existuje právě jedno ^-pravidlo S —» £ a 5 se nevyskytuje na pravé straně žádného pravidla z P. IB102 Automaty a gramatiky, 16.11.2009 1 Příklad IB102 Automaty a gramatiky, 16.11.2009 2 Algoritmus pro odstranění -pravidel Vstup: CFG Q = (7V,S,P,5) Výstup: CFG Q' = (Nf, E, P', S") bez ^-pravidel splní 2 Zkonstruuj 7V£ = {A G N \ A ^* č} 2 Množinu pravidel P' zkonstruuj takto: 3 foreach A —> X\... Xn G P do 4 přidej do P7 všechna pravidla tvaru A^a\...ans 5 (a) pokud Xi ^ N£ pak olí = JQ dL(g)=L(gf) ICI 6 7 8 od (b) pokud Xj G -/Ve pak c^ je bud Xj, nebo s (c) ne všechna on jsou e 10 9 if S G 7V£ then přidej do P' pravidla S" N' :=N\J {S'} else X' := N: S' := 5 fi S\e(S' ^JVUS); IB102 Automaty a gramatiky, 16.11.2009 3 55 55 g = ({S,A,B},{a,b,c},P,S) S - -> aAbBc AB A - -y BB a s B - -»• AA b IB102 Automaty a gramatiky, 16.11.2009 Příklad kde P obsahuje pravidla 4 Korektnost algoritmu Konečnost. Výsledná gramatika je bez ^-pravidel. Ekvivalence gramatik. IB102 Automaty a gramatiky, 16.11.2009 5 Jednoduchá pravidla Jednoduchým pravidlem nazývame každé pravidlo tvaru A—> B, kde A, B G N. S —» aAbBc A -► aA I B B ^ bB b a IB102 Automaty a gramatiky, 16.11.2009 6 Algoritmus pro odstranění jednoduchých pravidel Vstup: CFG g = (N, E, P, S) bez ^-pravidel Výstup: CFG Q' = (TV, E, P7, 5) bez jednoduchých a č-pravidel, kde L{Q) = L{Q') i foreach iGiVdo 2 i := 0; Ni := {A} 3 repeat i := i + 1 4 TVi := 7Vi_i U{C|B^CeP,Be A^-i} 5 until Ni = 7Vi_i 6 NA := JVť 7 od s P7 := 0 p foreach iGiVdo I0 P7 := P' U {4 u od a B G A^ A B^aGP není jednoduché} IB102 Automaty a gramatiky, 16.11.2009 7 Příklad g = ({S7A,B7C}7{aAc},P,S), kde P obsahuje pravidla S A B C ABC aA I B bB | A cC A a IB102 Automaty a gramatiky, 16.11.2009 8 Korektnost algoritmu Konečnost. Výsledná gramatika neobsahuje jednoduchá pravidla. Ekvivalence gramatik: L{Q') C L{Q) Necht w £ L{Q'), pak existuje derivace S = a0 =>gf ai =>gf . . . ^gf OLn = W. Pokud bylo při kroku cti =^g/ c^+i použito pravidlo A —» /3, pak existuje nějaké B G Na takové, že v Q platí A =^>* B a B ^ ß. Tedy v C? platí A =>* ß a c^ =>* c^+i. L{Q) C £(£/') Necht w^L{Q), pak existuje levá derivace Tu lze rozdělit na úseky tak, že v celém úseku se použila pouze jednoduchá pravidla anebo žádné jednoduché pravidlo. Úseky s jednoduchými pravidly lze nahradit. IB102 Automaty a gramatiky, 16.11.2009 9 Vlastní bezkontextová gramatika Definice 3.17. CFG Q = (TV, S,P, S) se nazývá necyklická, právě když neexistuje A G N takový, že A =^>+ A. Q se nazývá vlastní, právě když je bez nepoužitelných symbolů, bez e-pravidel a necyklická. Věta 3.18. Ke každému neprázdnému bez kontextové m u jazyku existuje vlastní bezkontextová gramatika, která jej generuje. Důkaz. Z bezkontextová gramatiky pro neprázdný jazyk odstraníme e-pravidla a jednoduchá pravidla. Odstraněním nepoužitelných symbolů pak získáme vlastní gramatiku. □ IB102 Automaty a gramatiky, 16.11.2009 10 Chomského normální forma Definice 3.19. Bezkontextová gramatika Q = (TV, S, P, S) je 7 f v Chomského normálni formě (CNF) & g je bez e-praviaei a každé pravidlo z P má jeden z těchto tvarů: 1. A^BC, kde P, C G TV 2. A —» a, kde a G S 3. S^ e Věta 3.21. Každý bez kontextový jazyk lze generovat bez kontextovo u gramatikou v Chomského normální formě. IB102 Automaty a gramatiky, 16.11.2009 11 Příklad IB102 Automaty a gramatiky, 16.11.2009 12 Lemma o substituci 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 ce, Definujme Q' = (TV, S, P', 5), kd< P7 = (P \ {A -> ceiPce2}) U {A -> axß\OL2 a1ßra2} Pak L{G) = L{G') IB102 Automaty a gramatiky, 16.11.2009 13 Algoritmus transformace do CNF 1. L = 0 2. L^0 Gramatiku pro L převedeme na vlastnia bez jednoduchých pravidel. X -»■ e X -»■ a X -> A X -> a& X -> aß X -»■ Ač> X -»• Aß X -»• aßcD IB102 Automaty a gramatiky, 16.11.2009 14 Lemma o vkládání pro bezkontextové jazyky Věta 3.24. Necht L je CFL. Pak existují p, g G N (závisející na Ľ) taková, že každé slovo z G L delší než p lze psát ve tvaru z = uvwxy, kde • alespoň jedno ze slov v, x je neprázdné (tj. vx ^ e), vwx < q a uvlwxly G L pro každé i gNq Poznámka 3.25. Tvrzení zůstává v platnosti i když namísto konstant p, g budeme všude psát jen (jedinou) konstantu n. IB102 Automaty a gramatiky, 16.11.2009 15 Důkaz Lemmatu o vkládání pro bezkontextove jazyky Necht L je generován gramatikou v CNF. délka cesty z kořene do listu = počet modrých hran = počet neterminálů na cestě - 1 hloubka stromu = maximální délka cesty Derivační strom hloubky k má max. 2k listů =>* slovo délky nejvýše 2k. Derivační strom pro slovo delší než 2k~ľ má cestu délky alespoň k. Tato cesta obsahuje alespoň k + 1 neterminálů. IB102 Automaty a gramatiky, 16.11.2009 16 Důkaz Lemmatu o vkládání pro bezkontextové jazyky Necht L generován gramatikou Q = (TV, £, P, S), která je v CNF. Označme k = card(N) a položme p = 2fc_1, q = 2fc. Necht ^ G L je slovo delší než p. Pak v libovolném derivačním stromu slova z existuje cesta délky alespoň k. Zvolme pevně jeden takový strom Tav něm (libovolnou) nejdelší cestu C. IB102 Automaty a gramatiky, 16.11.2009 17 Na cestě C lze zvolit tři uzly u\,U2,uz s vlastnostmi: 1. uzly u\,U2 jsou označeny týmž neterminálem, řekněme A, 2. u\ leží blíže ke kořenu než i/^, 3. us je list a 4. cesta z u\ do ^3 má délku nejvýše k. IBIO2 Automaty a gramatiky, 16.11.2009 18 IB102 Automaty a gramatiky, 16.11. 2009 19 Použití Lemmatu o vkládání pro bezkontextove jazyky Lemma o vkládání je implikace P =>* Q, kde P je výrok, že L je CFL a Q jsou uvedené vlastnosti. Obměnu Lemmatu o vkládání -iQ => -

1} 1. Pro libovolnou konstantu n G N 2. existuje slovo z G L delší než n takové, že 3. pro všechny slova u,v,w,x,y splňující z = uvwxy, vx t^ e a viral < n 4. existuje i G No takové, že uvlwxly 0 L > L není CF:L IB102 Automaty a gramatiky, 16.11.2009 21 55