16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Patrick87 Dec 5 '12 at 18:45
  • $\begingroup$ Note that this generalizes: the complement of $\{a^n b^n c^n d^n e^n\}$ is a CFG. $\endgroup$ – sdcvvc Dec 5 '12 at 19:41
  • $\begingroup$ Similar question. $\endgroup$ – Raphael Dec 6 '12 at 6:04
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'd written down these cases alright, but I was missing the idea to connect them. Thank you! $\endgroup$ – hauptbenutzer Dec 5 '12 at 18:42
  • 4
    $\begingroup$ Actually you need only any two cases. $\endgroup$ – sdcvvc Dec 5 '12 at 19:39
  • $\begingroup$ @sdcvvc Good point. :) $\endgroup$ – Patrick87 Dec 5 '12 at 20:24
  • $\begingroup$ For different number of characters, consider this as inspiration: $S → xSy | X | Y ; X → x | xX ; Y → y | yY$. It should be simple to glue either $a^+$ onto the left of this or $c^+$ onto the right and turn this into a PDA. For the tricky case (which you don't need) $S → aSc | A | C ; A →aB | aA ; C → Bc | Cc ; B → ε | bB$. $\endgroup$ – Jonas Kölker Jul 31 '16 at 12:02

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.