322 Study Guide: Old Final Exam Questions

1. Answer True or False to the following questions. You do not need to justify your answers. All strings considered are over some fixed alphabet Sigma.
   1. The complement of a CFL is never a CFL.
   2. For any context-free grammar G there is a PDA M such that G generates exactly the set of strings that M accepts.
   3. Any set of languages that is closed under union, concatenation, and Kleene star must be the regular languages.
   4. If K=L U M and both K and L are regular then so is M.
   5. If K is not a CFL and K=R intersect L where R is regular then L is not a CFL.
   6. If L=L(M) for some PDA M then both L and L^* are CFL's.
   7. If L subset K and L is a CFL then so is K.
   8. There exist some non-regular languages that are generated by CFG's.
   9. For every regular language L over Sigma there are strings x,y,z in Sigma^* such that |y|>= 1 and for every k>= 0, x y^k z is in L.
   10. If K and L are context-free languages then so is K intersect L.
2. Classify each of the following sets as:
   • [A] Both Regular and Context-Free,
   • [B] Context-Free, but not regular,
   • [C] Regular, but not context-free, or
   • [D] Neither context-free nor regular.
   You do not need to justify your answer. Unless otherwise specified it is assumed that w is in {a,b}^*.
   1. { w | w contains a different number of a's and b's}
   2. { w | w contains an even number of a's but does not contain abb as a substring}
   3. { aⁿ bⁿ a^m b^m | m,n >= 0}
   4. { aⁿ b^m aⁿ b^m | m,n >= 0 }
   5. { xcy | x is in {a,b}^* and y != x^R }
   6. { x | x is in {a,b}^* and |x|>= 100 }
   7. {aⁿ² | n >= 0}
   8. { w | w^R=w}
   9. { w | w^R != w}
   10. { w | w contains both abaa and aaba as substrings}
3. Let L={x in {0,1}^* | x has exactly twice as many 0's as 1's}
   • State the Pumping Lemma for Regular Languages (in the version that we proved and used in class.)
   • Prove that L is not a regular language.
4. Let G = (V,Sigma,R,S) be a context-free grammar, where Sigma = {a,b}, V = {S,T,a,b}, and R is S-> TS, S->a, T-> aTb, T->ab
   1. Give a parse tree for the string: aabba
   2. Write out the leftmost derivation corresponding to the parse tree in part (a).
   3. Use the general construction that converts a CFG to a PDA to give a PDA M such that L(M)=L(G). (Write out its full formal definition.)
   4. Show the computation of your PDA on the input aabba. Be sure to show the full configuration at each step.
5. Let B be the set of all strings over {(,)} with balanced parentheses. (Recall that this means that every prefix of the string has at least as many left parentheses, (, as right parentheses, ), and the string as a whole has an equal number of left and right parentheses.)
   1. Design a PDA M such that L(M)=B. Give its full formal definition.
   2. Modify your PDA from part (a) to produce a PDA M' such that L(M') consists of those strings in B with an even number of left parentheses. Give its full formal definition.
6. Prove that {a^k b^2k a^3k | k>= 0} is not a context-free language.
7. A substitution is a function f:Sigma₁ -> (Sigma₂)^* that associates a string f(a) over Sigma₂ with each symbol a in Sigma₁. We can extend this to a function that maps strings over Sigma₁ to strings over Sigma₂ by defining f(a₁ a₂ ... a_k)=w₁ w₂ ... w_k where f(a₁)=w₁, f(a₂)=w₂, ..., f(a_k)=w_k. (That is, from string x we obtain a new string f(x) by substituting strings for each symbol in x and concatenating the results together.)
   For L subset (Sigma₁)^* define f(L)={f(x) | x is in L}. Show that if L is a regular language then so is f(L).
8. This problem gives another proof that CFL's are not closed under intersection:
   • Prove that L₁={aⁱbⁱ⁺¹c^j | i,j >= 0} is a CFL.
   • Prove that L₂={aⁱb^jc^j+1 | i,j >= 0} is a CFL.
   • What is L=L₁ intersect L₂?
   • Prove that L=L₁ intersect L₂ is not a CFL.