# 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.

$L$ is not context free. You can use the Ogden's lemma to show it.

I'll use the Wikipedia notation linked above.

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$.

Hope it helps.

• Thank you so much. I'm assuming that the second piece a^nb^nc^2n can be disproved this way as well? Mar 11 '13 at 21:09
• yep same proof should even be easier.
– wece
Mar 11 '13 at 21:15
• It seems the standard Pumping for context-free languages would work fine. Either pump $a$'s and $b$'s up, or $c$'s down. Mar 12 '13 at 10:59
• @HendrikJan you are right. And its easier ...
– wece
Mar 12 '13 at 12:41