1
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.