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$

migrated from cstheory.stackexchange.com Mar 12 '13 at 4:21

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

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$
  • $\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 '13 at 21:09
  • $\begingroup$ yep same proof should even be easier. $\endgroup$ – wece Mar 11 '13 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$ – Hendrik Jan Mar 12 '13 at 10:59
  • $\begingroup$ @HendrikJan you are right. And its easier ... $\endgroup$ – wece Mar 12 '13 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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