Kanonické tvary bezkontextových gramatik ■ redukované bezkontextové gramatiky ■ gramatiky bez e-pravidel ■ gramatiky bez jednoduchých pravidel ■ Chomského normálni forma ■ gramatiky bez levé rekurze ■ Greibachové normální forma IB102 Automaty, gramatiky a složitost, 20.10.2014 1/22 Chomského normální forma Definice 3.19. Bezkontextová gramatika Q = (N, Z, P, S) je v Chomského normální formě (CNF), právě když Q je bez e-pravidel a každé pravidlo z P má jeden z těchto tvarů: □ A BC, kde B,C e N Q A^f a, kde a g T. Věta 3.21. Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Chomského normální formě. IB102 Automaty, gramatiky a složitost, 20.10.2014 2/22 Příklad G = ({S, A, B}, {a, b}, P, S), kde P obsahuje pravidla S AS | a 4 4fl j M | a B -+ b IB102 Automaty, gramatiky a složitost, 20.10.2014 3/22 Algoritmus transformace do CNF n l = % Gramatiku pro l převedeme na vlastní a bez jednoduchých pravidel. X ^ e X a X —ř A X ab X aB X ^ Ab X AB X -+ aBcD IB102 Automaty, gramatiky a složitost, 20.10.2014 4/22 Lemma o vkládání pro bezkontextové jazyky Věta 3.24. Nechť L je CFL. Pak existují p, q 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), m \vwx\ < q a ■ uv'wx'y g L pro každé / g N0. Poznámka 3.25. Tvrzení zůstává v platnosti i když namísto konstant p, q budeme všude psát jen (jedinou) konstantu n. IB102 Automaty, gramatiky a složitost, 20.10.2014 5/22 Důkaz Lemmatu o vkládání pro bezkontextové jazyky Nechť 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ž 2fc 1 má cestu délky alespoň k. Tato cesta obsahuje alespoň k + 1 neterminálů. IB102 Automaty, gramatiky a složitost, 20.10.2014 6/22 Důkaz Lemmatu o vkládání pro bezkontextové jazyky Nechť L je generován gramatikou Q = (N, Z, P, S), která je v CNF. Označme k = card(N) a položme p = 2fc 1, q = 2k. Nechť z g Lje 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 T a v něm (libovolnou) nejdelší cestu C. IB102 Automaty, gramatiky a složitost, 20.10.2014 7/22 Na cestě C lze zvolit tři uzly ív-i , u2, u3 s vlastnostmi: □ uzly ív-i , u2 jsou označeny týmž neterminálem, řekněme A Q ív-i leží blíže ke kořenu než u2 El L/3 je list □ cesta z ív-i do ív3 má délku nejvýše k IB102 Automaty, gramatiky a složitost, 20.10.2014 8/22 IB102 Automaty, gramatiky a složitost, 20.10.2014 Použití Lemmatu o vkládání pro bezkontextové 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í -.Q =>- -.P lze použít k důkazu, že nějaký jazyk L není CFL — stačí, když ukážeme platnost -iQ. □ Pro libovolnou konstantu neN B existuje slovo z e L delší než n takové, že B pro všechny slova u, v, w, x, y splňující z = uvwxy, vx ^ e a | vwx\ < n □ existuje / g N0 takové, že uv'wx'y 0 L. IB102 Automaty, gramatiky a složitost, 20.10.2014 10/22 Příklad použití Lemmatu o vkládání L = {aibici | /> 1} □ Pro libovolnou konstantu neN B existuje slovo z e L delší než n takové, že Q pro všechny slova u, v, w, x, y splňující z = uvwxy, vx ^ e a | vwx\ < n □ existuje / g N0 takové, že uv'wx'y 0 L. L není CFL. IB102 Automaty, gramatiky a složitost, 20.10.2014 11/22 Rekursivní neterminály a gramatiky Definice 3.28. Neterminál A v CFG Q = (N, Z, P, S) se nazývá levorekursivní jestliže v Q existuje derivace A A(3. CFG bez levorekursivních neterminálů se nazývá nelevorekursivní. Je-li v CFG pravidlo tvaru A Aa, hovoříme o přímé levé rekursi na A. Praktický význam: některé nástroje pro automatickou tvorbu parserů k zadaným gramatikám vyžadují na vstupu nelevorekursivní gramatiku (např. ANTLR). IB102 Automaty, gramatiky a složitost, 20.10.2014 12/22 Algoritmus odstranění přímé levé rekurze Nechť CFG Q = (N, Z, P, S) je necyklická a bez e-pravidel, v níž všechna /A-pravidla (pravidla mající na levé straně A) jsou tvaru A —> Aa-\ | ... | Aam \ /3-\ | ... | /3n, kde každý řetěz /3( začíná symbolem různým od /A. Nechť £' = (Nu {A'}, Z, P', S), kde P' obdržíme z P tak, že všechna výše uvedená pravidla nahradíme pravidly: \ ...\pn\M\---\PnA' A' —> a-\ | ... | am | a-\ Ä | ... | amÄ Pak L(Q) = L(Q') a Q' je necyklická a bez e-pravidel. IB102 Automaty, gramatiky a složitost, 20.10.2014 13/22 Lemma o substituci Lemma 3.20. (o substituci) Nechť G = {N, Z, P, S) je CFG. Nechť A -> aA Ba2 e P. Nechť B ->•/3-| | ... | /3r jsou všechna pravidla v P tvaru B ->• a. Definujme = (A/, Z, P, S), kde P' = (P \ {/A ->• a-|Sa2}) U {/A a-i/3-| a2 | ... | a-i/?,-^}. Pak L(0) = /.(£')■ IB102 Automaty, gramatiky a složitost, 20.10.2014 14/22 Příklad A -+ Bd | c B Bdd | Ccc | aAd C Aa IB102 Automaty, gramatiky a složitost, 20.10.2014 15/22 Algoritmus odstranění levé rekurze Vstup: Vlastní CFG Q = {N, Z, P, S) Výstup: Ekvivalentní nelevorekursivní gramatika bez e-pravidel 1: Uspořádej libovolně N, N = {A^,...,An} 2: for / <- 1 to n do 3: for y <- 1 to / - 1 do 4: for all pravidlo tvaru A, ->• Asa do 5: přidej pravidla ->• faa \ ... \ /3ka 6: (kde Aj ->•/3-| | ... | /3k jsou všechna pravidla pro Aj) 7: vypusť pravidlo ->• Aja 8: end for 9: end for 10: odstraň případnou přímou levou rekursi na 11: end for IB102 Automaty, gramatiky a složitost, 20.10.2014 16/22 Korektnost algoritmu Konečnost. Ekvivalence gramatik: Všechny úpravy jsou dle Lemmatu o substituci nebo odstraňují přímou levou rekursi. Výsledná gramatika je nelevorekursivní: □ po /-té iteraci vnějšího cyklu začíná každé A-pravidlo buď terminálem nebo neterminálem Ak, kde k > /'. B po y-té iteraci vnitřního cyklu začíná každé A-pravidlo buď terminálem nebo neterminálem Ak, kde k > j. Výsledná gramatika je bez e-pravidel. IB102 Automaty, gramatiky a složitost, 20.10.2014 17/22 Greibachové normální forma Definice 3.33. Bezkontextová gramatika Q = (N, Z, P, S) je v Greibachové normální formě (GNF), právě když ■ Q je bez e-pravidel a ■ každé pravidlo z P je tvaru A ->• aa, kde a g T. a a g A/* (s případnou výjimkou pravidla S e). Věta 3.34. Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Greibachové normální formě. IB102 Automaty, gramatiky a složitost, 20.10.2014 18/22 Zásobníkové automaty IB102 Automaty, gramatiky a složitost, 20.10.2014 19/22 Definice zásobníkového automatu Definice 3.36. Nedeterministický zásobníkový automat (PushDown Automaton, PDA) je sedmice M = (Q, Z, ľ, S, qo,Z0, F), kde ■ Q je konečná množina, jejíž prvky nazýváme stavy, ■ Z je konečná množina, tzv. vstupní abeceda, ■ r je konečná množina, tzv. zásobníková abeceda, ■ S : Q x (Z u {e}) xľ-í TfíhÍO x r*), tzv. (parciální) přechodová funkce1, ■ q0 e Q je počáteční stav, ■ Zo g r je počáteční symbol v zásobníku, ■ F c Q je množina koncových stavů. 1Zápis VnniQ x T*) značí množinu všech konečných podmnožin množiny Q x ľ*. IB102 Automaty, gramatiky a složitost, 20.10.2014 20/22 Výpočet zásobníkového automatu Definice 3.37. Nechť M = (Q, Z, r, ó, q0,Z0, F) je PDA. Konfigurací nazveme libovolný prvek (p, w, a) g Q x Z* x r*. Na množině všech konfigurací automatu M definujeme binární relaci krok výpočtu \-^- takto: def (p,aw,Za) Ym~ {q, w,7«) 3(qr,7) g