1. Construct a grammar G such that L(G) = L(M) where M is the PDA in the previous question. Then show that the word aaaabb is generated by G.

2. Prove, using the Pumping Lemma for Context-Free Languages, that the language L = {a^k | k is a perfect square} is not context-free.

2. Consider the language L = {a^k b^k | k > 0}. Explain whether this language is context-free, context-sensitive, recursive, recursively, enumerable, and/or regular. While formal proofs are not required, justify your assertions.