CS 172: Computability and Complexity, Spring 2010 S. A. Seshia & O. EtesamiHW 4: Context Free LanguagesAssigned: February 17, 2010 Due: February 24, 2010Note: Take time to write clear and concise solutions. Confused and long-winded answers may bepenalized. Consult the course webpage for course policies on collaboration.1. (3 points)Define the size of a context-free grammar to be the total number of characters used in writingthe rules of the grammar down (including variables, terminals, | and →). For example, theone-rule grammar A → A1 | ε has size six because it uses six characters.Consider a grammar that generates only the string “manamana banana” and no other strings.Here the set of terminals is the set of small letters in the English alphabet and the whitespacecharacter (denoted explicitly here by t), i.e., it is the set {a, b, c, ...,z, t} The smallestcontext-free grammar that generates only this string has size sixteen. Write the rules for thisgrammar.2. (9 points)Let Σ = {0, 1, #}. Design a context-free grammar that generates the language L = {x#y :x, y ∈ {0, 1}∗, x 6= y}. Explain why your grammar is correct.Also, give the state-diagram of a PDA that generates L. (No need to prove that your PDA iscorrect.)3. (12 points) Let G be a CFG in Chomsky Normal Form.(a) (4 points) Prove that, if w is a string in L(G) of length n where n ≥ 1, then anyderivation of w in G takes exactly 2n − 1 steps.(b) (8 points) Suppose G contains less than m variables. Prove that, if G generates a stringwith a derivation having at least 2msteps, L(G) is infinite.[Hint: Use part (a) and the statement and proof idea of the CFL pumping lemma.]4. (6 points) Recall the discussion we had in class about families of computer viruses that can becharacterized as languages. A computer program is viewed as a string of instructions drawnfrom a finite alphabet Σ. A language characterizes a subset (family) of virus programs.Suppose you work at anti-virus software company ImmuneSystems. You have already char-acterized the members of two virus families: one family is a context-free language A and thesecond is a regular language B. However, to foil your anti-virus software, the virus creators1have released a new “mutation” tool that generates a new family of programs defined as thefollowing language:L = {w | ∃x s.t. wx ∈ A and x ∈ B}You are tasked with updating your software to recognize the new virus language L. However,your co-worker Ignoramus complains that the detection problem is “too hard” because thereis no context-free grammar that can recognize L.Prove Ignoramus wrong; i.e., show that the set of new viruses is a context-free language.[Hint: Show how to construct a PDA or CFG generating the set of new viruses from A andB. You can use the equivalence of PDAs and CFGs if
View Full Document
Unlocking...