How do you show that the language $L= \{ a^nb^nc^na^kb^lc^m \mid l,m,n \geqslant 0 \text{ and } k >0 \}$ is not context-free.

Question

This is somewhat similar to another question I asked here. In that case you could apply the pumping lemma by pumping down on $a^nb^nc^nabc$ . However when $>$ is replaced by $\geq$ for all $\{k,l,m,n\}$, I think that option is no longer available. However, then you can pump up on $a^nb^nc^n$ and prove the required result quite easily. To cut off that possibility, just one power variable of $a^kb^lc^m$, i.e. one of $\{k,l,m\}$, in this case is kept to be greater than $0$, i.e. $k>0$. Can this grammar be shown to be not in cfg?

Answer 1

Suppose that $L$ is context-free. Then its intersection with the regular language $a^+b^+c^+a$ is also context-free. But $$ L \cap a^+b^+c^+a = \{a^nb^nc^na \mid n > 0\} $$ and you apparently already know how to handle this case. Thus $L$ is not context-free.