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, xy^kz 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} as a subset of (Sigma₂)^*. Show that if L is a regular language then so is f(L).