# Construct a PDA for the complement of $a^nb^nc^n$

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.

-
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
– Raphael Dec 6 '12 at 6:04

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.