Bezkontextové jazyky Bezkontextová gramatika (context-free grammar, CFG) Q je čtveřice (N, E, P, S), kde • N je neprázdná konečná množina neterminálních symbolů, • S je konečná množina terminálních symbolů taková, že N n S = 0 (značení: V = NUE)1 • S G N je počáteční neterminál, • P C TV x I/* je konečná množina pravidel. Jazyk je bezkontextový, pokud je generovaný nějakou bez kontextovo u gramatikou. IB102 Automaty a gramatiky, 9.11.2009 1 Příklad G = ({E,T,F}, {+,*,(,),i},P,E), kde P obsahuje pravidla E T F E + T T*F (E) | i T F IB102 Automaty a gramatiky, 9.11.2009 2 Derivační stromy pro bezkontextové gramatiky Definice 3.1. Necht Q = (TV, E, P, S) je CFG. Strom T nazveme derivačním stromem v Q právě když 1. kořen má návěští S, vnitřní uzly mají návěští z N, listy mají návěští z NU E U {e}, 2. má-li vnitřní uzel návěští A a jeho všichni synové ni,..., n& mají v uspořádání zleva doprava návěští Xl, ..., X& G y, pak 3. každý list s návěštím e je jediným synem svého otce. Výsledkem derivačního stromu T nazveme slovo vzniklé zřetězením návěští listů v uspořádání zleva doprava. IB102 Automaty a gramatiky, 9.11.2009 3 Vztah mezi derivačními stromy a relací * Věta 3.3. Necht Q = (TV, E, P, S) je CFG. Pak pro libovolné aG(JVU S)* platí 5 =^>* ce právě když v Q existuje derivační strom s výsledkem a. Důkaz. Označme Q a = (ÍV, £,P, A), kde A G N. Dokážeme, že pro každé A G N platí A =^>* ce «<=>* v ^ existuje derivační strom s výsledkem a (^=) Necht a je výsledkem derivačního stromu, který má k vnitřích uzlů. Indukcí vzhledem ke k ukážeme, že pak A =^>* a. Základní krok k = 1: IB102 Automaty a gramatiky, 9.11.2009 4 Indukční krok k > 1: (IP) Tvrzení platí pro stromy s k — 1 vnitřními uzly. Strom T s k uzly: • je-li Xi list, označme ai = Xi • není-li X^ list, pak ai je výsledkem podstromu Ti s kořenem • Výsledek T ]e a\... an. Platí: X^ =^>* c^ (pro X^, které není listem, podle (IP)) A —» Xi... Xn G P (z definice deriv. stromu) Dostá vame A =t> Xi ... Xn =t> o?i... an. IB102 Automaty a gramatiky, 9.11.2009 (=^) Necht A =^>* a. Ukážeme, že v Q a existuje derivační strom s výsledkem a. Použijeme indukci k délce odvození A =^>* a. Základní krok A => a: Pak a = A a odpovídající derivační strom má jen jeden uzel (kořen je list) s označením A. Indukční krok A => a, k > 0: (IP) Pro každé B G N platí: pokud B =^>* ß v nejvýše k krocích, pak v Qb existuje derivační strom s výsledkem ß. A => a =>* A => Xi... Xn => c*i... an, kde Xi ^> olí Konstrukce stromu s výsledkem a: D IB102 Automaty a gramatiky, 9.11.2009 6 Jednoznačnost derivačních stromů Derivace je sekvence S =>* a\ =>* 0L2 => • • • => <^n- Levá (resp. pravá) derivace je taková derivace, kde každé c^+i vzni z c^ přepsáním nejlevějšího (resp. nejpravějšího) neterminálu. Každému derivačnímu stromu odpovídá jediná levá derivace. Každé levé derivaci odpovídá jediný derivační strom. Analogicky pro pravou derivaci. Existuje pro každé a £ L(Q) právě jeden derivační strom? IBIO2 Automaty a gramatiky, 9.11.2009 Definice 3.7. CFG Q se nazývá víceznačná (nejednoznačná) právě když existuje w £ L(Q) mající alespoň dva různé derivační stromy. V opačném případě říkáme, že Q je jednoznačná. Jazyk L se nazývá vnitřně (inherentně) víceznačný právě když každá gramatika, která jej generuje, je víceznačná. IB102 Automaty a gramatiky, 9.11.2009 8 Kanonické tvary bezkontextových gramatik • redukované bezkontextové gramatiky • gramatiky bez ^-pravidel • gramatiky bez jednoduchých pravidel • gramatiky bez levé rekurze • Chomského normální forma • Greibachové normálni forma IB102 Automaty a gramatiky, 9.11. 2009 9 Redukované bezkontextove gramatiky Definice 3.7 Symbol X G N U S je nepoužitelný v CFG Q = (TV, S, P, S) právě když v č? neexistuje derivace tvaru S =^>* wXy =^>* ira^y pro žádné w,x,y G S*. Řekneme, že Q je redukovaná, jestliže neobsahuje žádné nepoužitelné symboly. X je nepoužitelý typu I (nenormovaný) <^^> neexistuje w G S* splňující X =>* w X je nepoužitelý typu II (nedosažitelný) <^> neexistují a,ß G (JVUE) splňující 5 ^*aX/3 IB102 Automaty a gramatiky, 9.11.2009 10 55 55 Nalezení nepoužitel (neexistuje w Vstup: CFG g = (N, E, P, S) Výstup: Ne = {A \ 3w G S*. A i i := 0; N0 := 0 2 repeat i := i + 1 3 Ni := 7Vi_i U {A | A - 4 until Ni = Ni-! s Ne := Ni IB102 Automaty a gramatiky, 9.11.2009 ných symbolů typu I e £*: A ^* w) a e P, a e {Ni-! U S)*} Věta. Necht Q = (N, E, P, S) je CFG taková, že L(Q) ^ 0. Položme G' = (Ne, S, P', 5), kde P7 = P n 7Ve x (7Ve U S)*. Pak Q1 je CFG bez nepoužitelných neterminálů typu I a L (Q) = L{Q')- Důkaz. Dokážeme A G Xe ^^ 3w G S*.A ^* w. (=>) Indukcí k i dokážeme A e Ni => 3w G S*. A =>* w Základní krok i = 0: Platí triviálně, protože TVq = 0. Indukční krok: (IP) Tvrzení platí pro i. Dokážeme pro i + 1. • A G Ni. Tvrzení plyne z (IP). • A G Ni+1 \ A^. Pak existuje A —> Xi... Xk G P, kde každé X, je terminál nebo neterminál patřící do A^. Podle (IP) existuje Wj tak, že Xj =^>* Wj. Tedy A => X\...Xk =^>* wiX2...Xk =^* ... =^* wi...Wk, kde wi.. .Wk G S*. IB102 Automaty a gramatiky, 9.11.2009 12 {<=) Indukcí k n dokážeme i^w;,w]GS* =>* A G Ni pro nějaké i Základní krok n = 1: A —» w G P okamžitě dává i = 1. Indukční krok: (IP) Předpokládejme, že dokazované tvrzení platí pro všechna n' < n. \ŕ yi —I— 1 yi i" i Necht A => w. A => X\... Xk => w, kde Xj => ^ a n^ < n. Pokud X j G N, pak podle (IP) Xj G A^. pro nějaké i,. Pokud Xj G S, klademe ij = 0. Položme i = 1 + max{ii,..., i^}. Pak zřejmě A G Ni. D IB102 Automaty a gramatiky, 9.11.2009 13 Důsledek 3.10. Existuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L{Q) = 0. Důkaz. Stačí ověřit, zda S £ Ne. □ IB102 Automaty a gramatiky, 9.11.2009 14 Nalezení nepoužitelných symbolů typu II (neexistují a, ß G (N U E)* : S ^>* aXß) Vstup: CFG G = (N, S, P, S) Výstup: CFG Q' = (N', T,', P', S) bez nedosažitelných symbolu splňující L(G) = L{Q') ! i := 0; Vi := {S} 2 repeat i := i + 1 s V := Vi-! U{IeiVUS|3ie Vi-!. A -»■ a'A"/?' G P} 4 until Vi = Vi-! s N' := N n V-; S' := S n V-; P' := P n (V- x V"/) Korektnost: IgJV'uS' ^^ 3a,/5 G (JV U E')* • 5 =^* aX/5 IB102 Automaty a gramatiky 9.11.2009 15 55 Příklad IB102 Automaty a gramatiky, 9.11.2009 16 Eliminace nepoužitelných symbolů Věta 3-11- Každý neprázdný bezkontextový jazyk L je generován nějakou redukovanou CFG. Důkaz. Necht L je generován nějakou CFG Q. Krok 1. Z Q odstraníme symboly typu I (výsledek označme Gi)- Krok 2. Z Qi odstraníme symboly typu II (výsledek označme Q2). IBIO2 Automaty a gramatiky, 9.11.2009 17 Korektnost: Sporem dokážeme, že Q2 je redukovaná CFG. Předpokládejme, že G2 má nepoužitelný symbol X. • v C/2 existuje derivace S =>g ceX/3 • všechny symboly z ^2 jsou též v Q\ • pro nějaký terminálni řetěz w platí 5 =^ aXß =>g w • žádný symbol z derivace ceX/3 =^ w není krokem 2 eliminován a proto ceX/3 =>£ w Víme tedy, že existuje derivace S =>g aXß =>£ w, kde w je terminálni řetěz. To je ve sporu s předpokladem, že X je v Q2 nepoužitelný. □ IBIO2 Automaty a gramatiky, 9.11.2009 18