Q72: DFA of complement of regular language

Question 72: If M is a DFA accepting a language P. How can the DFA of complement of the regular language P be constructed?

1. The complement of a regular language is not regular, hence DFA of the complement can’t be constructed.
2. The complement of a regular language is regular, but however, its DFA can’t be constructed.
3. The DFA of the complementary language can be constructed by reversing the transitions of DFA.
4. The DFA of the complementary language can be constructed by exchanging the final and non-final states.

Solution: All of the strings which were accepted by M should not be accepted by new DFA, hence the final states become non-final. Similarly, all of the strings which were not accepted by M should be accepted by new DFA, hence non-final states become final states. Hence, the correct answer is option 4.