cs302 Theory of Computation UVa Spring 2008Notes: Context-Free LanguagesThursday, 14 FebruaryUpcoming ScheduleMonday, 18 February: Office Hours (Olsson 236A, 2-3pm); Help Session (Ols-son 228E, 5:30-6:30pm)Monday, 18 February (3:30pm): Annie Anton, North Carolina State University,Designing Legally Compliant Software Systems that Contain Sensitive Informa-tion (Department Colloquim in Olsson 009)Tuesday, 19 February (2:02pm): Problem Set 3Thursday, 28 February: Exam 1 (in class)Context-Free GrammarsA grammar is context-free if all production rules have the form: A → αγβ (that is, the leftside of a rule can only be a single variable; the right side is unrestricted and can be anysequence of terminals and variables).We can define a grammar as a 4-tuple (V, Σ, R, S) where V is a finite set (variables), Σ is afinite set (terminals), S is the start variable, and R is a finite set of rules, each of which is amapping V → (V ∪ Σ)∗.Example. (Similar to Sipser’s Exercise 2.9) Give a context-free grammar that generatesthe languageaibjck|i = j or i = k where i, j, k ≥ 0. Show how abbc is derived by yourgrammar. Show why aaabbc could not be derived by your grammar.Model of Computation for CFGsFirst, we describe the model of computation for CFGs using a function notation (not thetraditional ⇒ notation).Note that the grammar rules may have the same variable on the left side of may rulesin R, so we cannot interpret R as a function. Instead, we define the function δ whichcaptures the set of all right sides of rules for a given variable. The transition functionδ : V → P((V ∪ Σ)∗) (note the powerset operator - the output is a set of (V ∪ Σ)∗strings)is defined by:δ(A) = {α|α ∈ (V ∪ Σ)∗∧ A → α ∈ R}NCFL-1Then, as with DFAs, we can define the extended transition function δ∗recursively:δ∗(α) = {α} ∪[β∈δ(α)δ∗(β)A string w is in G = (V, Σ, R, S) iff w ∈ δ∗(S).Derivation. A more traditional way to define the model of computation for CFGs is usingderivation. A grammar G derives a string w if there is a way to produce w starting from Sfollowing the rules in R. S ⇒∗w means G derives w. We define the ⇒∗function somewhatsimilarly to the δ∗.First, we define ⇒, the one step derivation function in terms of R, the rules of the CFG:If A → γ is in R, then αAβ ⇒ αγβ for α, β, γ ∈ (V ∪ Σ)∗.That is, if there is a rule A → γ in R, anywhere A appears in a sequence of variables andsymbols, we can replace the A with γ, leaving the rest of the string unchanged.Now, we can define ⇒∗: (V ∪ Σ)∗→ (V ∪ Σ)∗, to mean that there is some way to producethe right side following zero of more steps starting from the input string (we can think of⇒∗as outputing a set of strings, but define it using just single strings on the output side;the actual value of derives(α) is the set of all strings:α ⇒∗α — any string derives itself (no replacements done).α ⇒∗γ if α ⇒∗β and β ⇒ γ — if we can go from α to β in zero or more steps,and from β to γ in one step, then we can derive γ from α.The string w is in the language defined by the context-free grammar G = (V, Σ, R, S) iff:S ⇒∗wProving Non-Context-FreenessTo show a language is not context-free, we need to prove there is no Context-Free Grammarthat can generate the language. The strategy is similar to how we used the pumping lemmato show a language is non-regular. The pumping lemma for context-free languages givesus a property that must be true of any context-free language. We get a contradiction, butshowing that there is no way to satisfy the properties of the pumping lemma for the given(non-context-free) language.NCFL-2Pumping lemma for context-free languages. For any context-free language A, there isa pumping length p where all strings s ∈ A with |s| ≥ p may be divided into 5 pieces,s = uvxyz satsifying these conditions:1. for each i ≥ 0, uvixyiz ∈ A2. |vy| > 03. |vxy| ≤ pSuppose there is a CFG G that generates A. Then any string s ∈ A can be derived usingG. Since G is a context-free grammar, each production rule has a single variable on theleft side. That means in a derivation of k steps (where each step involves replacing onevariable with the right hand side of a corresponding rule) if k ≥ |V | then some variableR ∈ V must be replaced twice:S ⇒∗uRz ⇒∗uvRyz ⇒∗uvxyzThe first replacement is R ⇒∗vRy, which can be repeated any number of times, producingviRyi.Example. D = {ww|w ∈ {0, 1}∗}.Assume D is a context-free language. Then, there must be a CFG G that pro-duces D, and the pumping lemma for context-free languages applies withpumping length p. As with pumping lemma for regular languages, we needto find one string w where |w| ≥ p, and show that it cannot be pumped.Pick w =Show that all possible ways of dividing w = uvxyz fail to satisfy the pumpinglemma for CFLs requirements.Tricky Example. Is X = {w|w ∈ {0, 1}∗∧ there is no z ∈ {0, 1}∗such that w = zz}