Given a DFA with multiple Final states. How can I find its compliment?

155 Views Asked by At

It is not possible to have multiple start state in DFA but how can I achieve Compliment operation on DFA having multiple Final states?

I try Complimenting the language of given DFA but how multiple final states can be converted to multiple starting states

1

There are 1 best solutions below

0
Patrick87 On

As pointed out in the comments, finding a DFA for compliment of the language of another DFA is quite straightforward: you simply make all accepting states non-accepting, and vice-versa. The resulting DFA may not be minimal for the language it accepts, but it is still a DFA.

You might be thinking of how to find a DFA for the reversal of a language of another DFA. This is a little more involved and encounters the issue you suggest: by reversing the direction of all transitions, making the initial state accepting and making accepting states initial, you get an automaton that works, but it has multiple initial states. This is not allowed for DFAs. Happily, we can make an NFA-lambda easily by adding a new state q0' and adding empty/lambda/epsilon transitions from it to the otherwise initial states. Now we have an NFA-lambda for the reversal of the language and we can obtain a DFA by determinizing this using a standard algorithm.