17
$\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$
4
  • $\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, 2012 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, 2012 at 19:41
  • $\begingroup$ Similar question. $\endgroup$
    – Raphael
    Dec 6, 2012 at 6:04
  • $\begingroup$ Is not the title of this question wrong? E.g. the complement of $\{a^n b^n c^n | n \geq 0\}$ is not $\{a^*b^*c^* - \{a^n b^n c^n | n \geq 0\}\}$. $\endgroup$
    – O. Altun
    May 30, 2020 at 13:13

1 Answer 1

17
$\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$
4
  • $\begingroup$ I'd written down these cases alright, but I was missing the idea to connect them. Thank you! $\endgroup$ Dec 5, 2012 at 18:42
  • 4
    $\begingroup$ Actually you need only any two cases. $\endgroup$
    – sdcvvc
    Dec 5, 2012 at 19:39
  • $\begingroup$ @sdcvvc Good point. :) $\endgroup$
    – Patrick87
    Dec 5, 2012 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$ Jul 31, 2016 at 12:02

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.