Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $\{a^*b^*c^*\}$ might as well accept it, which sounds contradictory to me.

I guess I need to take advantage of the non-deterministic nature of PDAs but I'm out of ideas. If you could offer some advice I would very much appreciate it.

share|cite|improve this question
Interesting point about it seeming contradictory. Indeed, context-free languages are not closed under taking the complement... so there are lots of examples of non-context-free languages that could be "accepted" in the sense you allude to. I'm not a theorist and, as such, can't really reconcile this, but perhaps someone else can chime in on why this isn't something to worry about? – Patrick87 Dec 5 '12 at 18:45
Note that this generalizes: the complement of $\{a^n b^n c^n d^n e^n\}$ is a CFG. – sdcvvc Dec 5 '12 at 19:41
Similar question. – Raphael Dec 6 '12 at 6:04
up vote 14 down vote accepted

No, this is context-free. To accept $a^nb^nc^n$, you need to make sure that three numbers are equal. To accept $a^*b^*c^* \setminus a^nb^nc^n$, you just need to make sure that you're in one of the following three cases:

  1. The number of $a$s is different from the number of $b$s; or
  2. The number of $a$s is different from the number of $c$s; or
  3. The number of $b$s is different from the number of $c$s.

Write a PDA for each of these cases, then combine them by jumping nondeterministically to each one from the start state.

share|cite|improve this answer
I'd written down these cases alright, but I was missing the idea to connect them. Thank you! – hauptbenutzer Dec 5 '12 at 18:42
Actually you need only any two cases. – sdcvvc Dec 5 '12 at 19:39
@sdcvvc Good point. :) – Patrick87 Dec 5 '12 at 20:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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