Please write your solutions as clearly and concisely as possible.

1. (60 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} where "n >= 0" means "n greater than or equal to 0".
   2. L = {aⁿbⁿ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
   
   
2. (40 pts) Give the diagram of a Turing machine that accepts the language L = {a^kb^mc^kd^m | k, m >= 0}

   ---