Bezkontextové jazyky Bezkontextová gramatika (context-free grammar, CFG) G je čtveřice (N, S,P,S), kde • N je neprázdná konečná množina neterminainích symbolů, • S je konečná množina terminainích symbolů taková, že N n S = 0 (značení: V = N U S), • S G N je poCateCní neterminai, • P C N x V * je konečná množina pravidel. Jazyk je bezkontextovy, pokud je generovaný nejakou bezkontextovou gramatikou. IB102 Automaty a gramatiky, 1.11.2010 1 Příklad Q = ({E, T, F}, {+, *, (,), i}, P, E), kde P obsahuje pravidla E E + T | T T — T * F | F F — (E) | i IB102 Automaty a gramatiky, 1.11.2010 2 Derivační stromy pro bezkontextové gramatiky Definice 3.1. Necht G = (N, S, P, S) je CFG. Strom T nazveme derivačním stromem v G prave když 1. koren ma navest í S, vnitrn í uzly maj í navest í z N, listy maj í navest í z N U S U {č}, 2. ma-li vnitrn í uzel navest í A a jeho vsichni synove n\,..., n& maj í v usporadan í zleva doprava navest í Xi,..., Xk G V, pak A —> Xi... X k G P, 3. kazdy list s navest ím e je jedinym synem sveho otce. Výsledkem derivaCn ího stromu T nazveme slovo vznikle zretezen ím navest í listu v usporadan í zleva doprava. IB102 Automaty a gramatiky, 1.11.2010 3 Vztah mezi derivačními stromy a relací Věta 3.3. Necht G = (N, S, P, S) je CFG. Pak pro libovolné a G (N U S)* platí S =^>* a pravé když v G existuje derivaCní strom s výsledkem a. Důkaz. OžnaCme G a = (N, S, P, A), kde A G N. Dokažeme, že pro každe A G N platí A =^>* a v GA existuje derivaCní strom s výsledkem a (^^) Necht a je výsledkem derivaCního stromu, který ma k vnitrích užlU. Indukcí vžhledem ke k ukažeme, že pak A =^>* a. Zakladní krok k = 1: IB102 Automaty a gramatiky, 1.11.2010 4 Indukční krok k > 1: (IP) Tvrzen í plat í pro stromy s nejvýše k — 1 vnitrn ími uzly. Strom T s k uzly: • je-li Xi list, označme oi — Xi • nen í-li Xi list, pak oi je výsledkem podstromu Ti s kořenem Xi • Výsledek T je Plat í: Xi =^>* oi (pro Xi, ktere nen í listem, podle (IP)) A — Xi... Xn G P (z definice deriv. stromu) Dostávame A X1... Xn =^>* o1 ... on. IB102 Automaty a gramatiky, 1.11.2010 5 (=^>) Necht A =^>* a. Ukážeme, že v Qa existuje derivační strom s výsledkem a. Použijeme indukci k delce odvožen í A =^>* a. Základní krok A 4> a: Pak a = A a odpov ídaj íc í derivačn í strom má jen jeden užel (koren je list) s označen ím A. Indukční krok A k=> a, k > 0: (IP) Pro každe B G N plat í: pokud B =^>* (3 v nejvýse k kroc ích, pak v Qb existuje derivacn í strom s výsledkem (3. A k=+ a =^> A X1... Xn 4> ai... an, kde Xi ^> ai Konstrukce stromu s výsledkem a: □ IB102 Automaty a gramatiky, 1.11.2010 6 Jednoznačnost derivačních stromů Derivace je sekvence S a1 =>* a2 =>* ... =>* an. Leva (resp. prava) derivace je takova derivace, kde každe * wXy =^>* wxy pro žadne w,x,y G S*. Řekneme, že Q je redukovaná, jestliže neobsahuje žadne nepoužitelne symboly. X je nepouZitely typu I (nenormovaný) neexistuje w G S* splnujŕcf X =^>* w X je nepouZitely typu II (nedosaZitelny) neexistujŕ a, P G (N U S)* splnujŕcf S =>* aXP IB102 Automaty a gramatiky, 1. 11. 2010 10 Nalezen í nepoužitelných symbolů typu I (neexistuje w G Ľ*: A ==* w) Vstup: CFG G = (N, S, P, S) Výstup: Ne = {A | 3w G S*. A ==* w} 1 i := 0; N0 := 0 2 repeat i := i + 1 3 Ni := Nť_i U {A | A — a G P, a G (Ni— U S)*} 4 until N = Ni_1 5 Ne := Ni IB102 Automaty a gramatiky, 1.11.2010 11 Věta. Necht Q = (N, S, P, S) je CFG taková, že L(Q) = 0. Položme G7 = (Ne, S, P', S), kde P' = P n Ne x (Ne U S)*. Pak Q7 je CFG bež nepoužitelných neterminálů typu I a L(Q) = L(Q'). Důkaz. Dokážeme A G Ne 3w G S*.A ^* w. (=>) Indukc í k i dokážeme A G Ni ==>- 3w G S*. A =>* w Zakladn í krok i = 0: Plat í triviálne, protože N0 = 0. Indůkcn í krok: (IP) Tvržen í plát í pro i. Dokážeme pro i + 1. • A G N{. Tvržen í plyne ž (IP). • A G Ni+1 \ Ni. Pák existuje A —> X1 ...Xk G P, kde kážde Xj je terminál nebo neterminál pátr íc í do Ni. Podle (IP) existuje Wj ták, že Xj =^>* Wj. Tedy A X1... Xk =^>* w1X2 ...Xk =^>* ... =^>* w1... wk, kde w1... wk G S*. IB102 Automáty á grámátiky, 1.11.2010 12 Indukčí k n dokázeme A w, w G S* A G N pro nejake i Zakladní krok n = 1: A — w G P okamzite dává i = 1. IndůkCn í krok: (IP) Předpokládejme, ze dokazovane tvrzení platí pro vSečhna n7 < n. Nečht A w. A X1... Xk =>* w, kde X j Wj a nj < n. Pokud Xj G N, pak podle (IP) Xj G Nij pro nejake ij. Pokud Xj G S, klademe ij = 0. Polozme i = 1 + max{i1,..., ik}. Pak zrejme A G N^. □ IB102 Automaty a gramatiky, 1. 11. 2010 13 Důsledek 3.10. Existuje algoritmus, ktery pro libovolnou danou CFG Q rozhoduje, zda L(Q) = 0. Důkaz. Stací overit, zda S G Ne. □ IB102 Automaty a gramatiky, 1. 11. 2010 14 Nalezení nepoužitelných symbolů typu II (neexistují a, // G (N U S)* : S ^* aX/?) Vstup: CFG G = (N, S, P, S) Výstup: CFG G' = (NS', P', S) bez nedosažitelných symbolů splňuj íc í L(G) = L(G') 2 i := 0; Vi := {S} 2 repeat i := i + 1 3 V, := Vi_i U {X G N U S | 3A G V_i. A — a'X/?' G P} 4 until V = Vi_1 5 N' := N n V,; S' := S n V,; P' := P n (V x V/) Korektnost: X G N' U S' ^ 3a, // G (N' U S')*. S aX// IB102 Automaty a gramatiky, 1.11.2010 15 Příklad G = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla S — aSb | c | aB A — dA | d B — eB IB102 Automaty a gramatiky, 1. 11. 2010 16 Eliminace nepouzitelných symbolů Veta 3.11. Kazdy neprazdny bezkontextovy jazyk L je generovan nejakou redukovanou CFG. Důkaz. Necht L je generovan nejakou CFG Q. Krok 1. Z Q odstran íme symboly typu I (výsledek označme Qi). Krok 2. Z Qi odstran íme symboly typu II (výsledek označme Q2). IB102 Automaty a gramatiky, 1. 11. 2010 17 Korektnost: Sporem dokažeme, že G2 je redukovana CFG. Predpokladejme, že G2 ma nepoužitelný symbol X. • v G2 existuje derivace S =^g2 oX/3 • vsechny symboly ž G2 jsou tež v Gi • pro nejaky terminalní retež w platí S =^2 oX^ w • žadny symbol ž derivace oX^ w není krokem 2 eliminovan a proto