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??


closed as unclear what you're asking by David Richerby, Evil, Tom van der Zanden, Rick Decker, Juho Sep 12 '16 at 15:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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 '16 at 6:19

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$ – Hendrik Jan Sep 13 '16 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 '16 at 17:32

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