# Complement of DPDA

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 ?

## 1 Answer

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.

• 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 ? – Sagar P Oct 24 '17 at 6:55
• 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. – Yuval Filmus Oct 24 '17 at 7:39
• 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? – Sagar P Oct 24 '17 at 9:01
• There are many possible definitions of DPDA. Only you know which one is used in your class. – Yuval Filmus Oct 24 '17 at 9:11
• Also what do you exactly mean by symmetric with respect to acceptance and non acceptance – Sagar P Oct 24 '17 at 9:37