Please write your solutions as clearly and concisely as possible.

1. (50 pts) For each of the following languages, give a pushdown automaton that accepts it, and say whether the automaton is deterministic or not. Try to give a deterministic automaton whenever possible.

   1. L = L(G) where G is the grammar

         S -> lambda | ( S ) S
      

      Note: L is the language of the balanced parentheses.

   2. L = { x in {a,b}^* | #_a(x) = #_b(x) }

   3. L = { aⁿx | n >=0, x in {a,b}^*, and |x| = n } where "n >= 0" means "n greater than or equal to 0", and |x| is the length of x.

2. (50 pts) For each of the following languages, say whether it is context-free or not, and prove your answer. (If the language is context-free, the proof can be done by defining the corresponding CFG or PDA. If the language is not context-free, the proof can be done as a proof-by-contadiction via the pumping lemma.)

   1. L = {aⁿbⁿaⁿ | n >= 0}

   2. L = {aⁿaⁿbⁿ | n >= 0}

   3. L = {xx^~ | x in {a,b}^*} where x^~ represents the string obtained from x by changing all a's in b's and viceversa. Example: if x = aaba then x^~ = bbab