# Is the following language context free?

Is $L = \{ a^nb^nc^j \mid n \le j\}$ a context-free language? I'm getting really stuck generating a grammar for it. Any help would be appreciated.

## migrated from cstheory.stackexchange.comMar 12 '13 at 4:21

This question came from our site for theoretical computer scientists and researchers in related fields.

$L$ is not context free. You can use the Ogden's lemma to show it.
For every $p$ take the word $a^pb^pc^p$. For a the marking where only c are marked whatever the decomposition $uxyzv$ you take, $ux^iyz^iv$ will not be in $L$. Four cases: $z\in c^*$ then it fails for $i=0$ or $z\notin c^*$ then it fails for $i>0$. And the symmetric cases for $x$.
• It seems the standard Pumping for context-free languages would work fine. Either pump $a$'s and $b$'s up, or $c$'s down. – Hendrik Jan Mar 12 '13 at 10:59