1. Write a CFG for the complement of {a^n b^n : n >= 0 }.
The complement language can be written as :
  strings containing ba
  strings of type a*b* and having more a than b
  strings of type a*b* and having more b than a
 

2. You are given two DFAs M1=<Q1,S,d1,q01,F1> and M2=<Q2,S,d2,q02,F2>.Construct a PDA=<...> for the language  {w=xy : there exists strings x and y such that |x|=|y|, x is in L(M1) and y is in L(M2) }.
  Non-deterministically guess the location at which to switch from simulating d1 to simulating d2. While simulating d1, push something in the stack and while simulating d2, pop it. Ask the students to write down all the components of the PDA, especially its transition function, in terms of d1 and d2.

3. Show that L = { binary string w : #(0,w) = 2*#(1,w) } is a CFL by constructing a PDA and (b*) constructing a CFG for L. Trace the PDA on the string 001001100 (show the IDs).

Hint: Let diff=2*#(0,w)-#(1,w). For the PDA, keep track of |diff| in the stack and sign(diff) in the state.

Store + or - in the state. Say, sign(diff) is +; now, seeing a 0, keeps the sign as +, and diff increases by 2, so push 2 symbols (of something). Similarly, try the other cases.

4. Show that a language L is regular if and only if L=L(G) for some CFG on which every production is of the form A -> cB or A -> e where A,B are variables and c is a terminal (e denotes the empty string).

Hint: Try some examples. For example, consider a DFA for L = {a,b}*ba and let G = S -> aS | bA , A -> bA | aB , B -> bA | aS.

This is the standard method to create a CFG from a DFA.

5*. Suppose a PDA never pushes more than k symbols on its stack on any input. Show that the language accepted by the PDA is regular.