Which one of these language Context free?

Question

Which one of the following languages is CFL and what is the grammar for it? Can we use pumping lemma for the not CFL?

\begin{align*} L_1 &= \{a^mb^ma^n \mid m,n \geq 0\}\\ L_2 &= \{a^mb^ma^n \mid m \geq n \geq 0\} \end{align*}

Answer 1

It’s very easy to write a context-free grammar that generates $L_1$. You might start with a production $S\to PA$ and add productions ensuring that $P$ generates $\{a^nb^n:n\ge 0\}$ and $A$ generates $a^*$.

Yes, you can use the pumping lemma for context-free languages to show that $L_2$ is not context-free; the proof is very similar to the usual example of such a proof, the proof that $\{a^nb^nc^n:n\ge 0\}$ is not context-free.