Search code examples
finite-automatacomputation-theorydeterministic

If a DFA is minimized, is it guaranteed that it's complement is also minimized?

Consider there is a minimized DFA that accepts the language L. The problem is to find the minimum number of states in its complement.

Now if I take the complement of this DFA i;e if I make the non-final states as final and final states as non-final, do I also need to worry about minimizing this complemented DFA?

DFA - Deterministic Finite Automata

Solution

  • Lets start with that L1 is accepted by a minimum DFA D1. Then we can retrieve the DFA of the complement (as you have mentioned). So let's derive a DFA D2 which accepts L1' which has the same amount of states as L1 .

    Now Lets assume that D2 is not a minimum DFA of L1'

    we should be able to reduce the number of states in it further to get a DFA D3. But getting the complement of D3 should give us a new DFA D4 which accepts (L1')' which is L1 but has less states than D1 making it not a minimum DFA of L1.

    So our assumption that D2 not being the miniumum of L1' is wrong.