1
$\begingroup$

I read that we can find complement of DPDA by just complementing(toggling) the states of DPDA.

Why can't we do the same with NPDA ?

Also is DCFL closed under complement just because we can toggle the states of DPDA ?

$\endgroup$
3
$\begingroup$

The semantics of deterministic automata is symmetric with respect to acceptance and non-acceptance. The same doesn't hold for non-deterministic automata: a non-deterministic automaton accepts a word if it accepts on some computation path, but it rejects a word if it rejects on all computation paths. This is why complementing the set of accepting states works for deterministic automata but not for non-deterministic automata.

I suggest picking a simple example and seeing what goes wrong. For example, consider the following NFA:

Sample NFA

This NFA accepts $\Sigma^*$. If we complement its set of accepting states, it still accepts $\Sigma^*$.

Finally, you ask whether the family of deterministic context-free languages is closed under complementation. This is indeed the case, for the reason you mention: given a DPDA for a language, if we complement the set of accepting states then we get a DPDA for the complement of the language. The same doesn't work for general PDAs, and indeed there are context-free languages whose complement isn't context-free.

$\endgroup$
  • $\begingroup$ I constructed a DPDA for L = {a^n b^n | n>=1} with 2 states . When I complemented the states, it was not able to accept strings like aabaa which belongs to complement of L. So even though I complemented DPDA but this DPDA is not accepting all strings in complement of L. Why is it so ? $\endgroup$ – Sagar P Oct 24 '17 at 6:55
  • $\begingroup$ Complementation only works for certain definitions of DPDAs. In particular, you will need a "dead state". The idea is that you should be able to reach the end of the word on every input word. $\endgroup$ – Yuval Filmus Oct 24 '17 at 7:39
  • $\begingroup$ So for complement to work, in each state of DPDA, we must define transitions for all input symbols right ? But in general we need not define transitions for every symbol in a particular state for DPDA right? $\endgroup$ – Sagar P Oct 24 '17 at 9:01
  • $\begingroup$ There are many possible definitions of DPDA. Only you know which one is used in your class. $\endgroup$ – Yuval Filmus Oct 24 '17 at 9:11
  • $\begingroup$ Also what do you exactly mean by symmetric with respect to acceptance and non acceptance $\endgroup$ – Sagar P Oct 24 '17 at 9:37

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.