If A & B are regular languages, prove that complement of A is also regular language. (Closure of regular languages under complementation)

Can anyone help me with the proof??

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Wikipedia provides a citation for this result: en.wikipedia.org/wiki/Regular_language#Closure_properties, and I'd expect it to be explained in many textbooks. $\endgroup$
    – D.W.
    Sep 12, 2016 at 6:19

1 Answer 1


If a language is indeed regular that means there is an FA that accepts it. The complement of L is just the language of all words that are not in L.

Thanks to Rick Decker for mentioning in the comments that this only works for FAs that are deterministic and to D.W for correcting the answer.

Now, a trick we can perform to test that the complement of L, namely L', is actually regular is to take the FA that accepts L and reverse all final states to non-final states and all non-final states to final states. Note that start states in the old FA become start and final states in the new FA.

This new FA will then accept all words present in L' which are words not in L.

In conclusion, take the FA accepting L and then form a new FA by:

  • Changing all final states to non-final states
  • Changing all non-final states to final states

The new FA accepts all words not in L, which is the language L'.

  • 1
    $\begingroup$ But then I would expect to swap between final states and non-final ones. Deterministic machines usually have a single start state that does not change or complementation. $\endgroup$ Sep 13, 2016 at 8:07
  • $\begingroup$ This answer is incorrect. You don't want to swap final states and start states; you want to swap final states and non-final states. Please edit the answer to correct it, and to state the requirement that the FA be deterministic up at the start (not just add an extra line at the end). $\endgroup$
    – D.W.
    Sep 13, 2016 at 17:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.