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 ?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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:
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.