If a language X regular, then is the complement of X also a regular language? If yes, then thank you, else can you please explain why

  • 2
    $\begingroup$ I truly hope this was covered in class. $\endgroup$ – Yuval Filmus Aug 5 '17 at 22:11
  • 1
    $\begingroup$ The body of your question doesn't match the title or the tags. Please edit to fix. $\endgroup$ – D.W. Aug 6 '17 at 4:53
  • $\begingroup$ cs.stackexchange.com/q/13282/755 $\endgroup$ – D.W. Aug 6 '17 at 4:55
  • $\begingroup$ @YuvalFilmus how is your comment constructive? If you are not answering the question, what is the point of leaving a comment there? what are you trying to achieve? $\endgroup$ – nikolaevra Aug 7 '17 at 13:54
  • $\begingroup$ This is truly bog-standard fare in a first course in automata theory. You should have seen this in class. If not, it is covered (under "closure properties of regular languages") all over the place. $\endgroup$ – vonbrand Mar 27 at 17:13

Yes, the complement of a regular language is regular. If $L$ is regular then there is a DFA accepting that language. In particular, its states can be classified as ACCEPTING states and non-ACCEPTING states. Just turn non-ACCEPTING states into ACCEPTING, and ACCEPTING states into non-ACCEPTING states and you will have a DFA accepting $\overline{L}$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thank you for the answer, and for explaining how to create a complement of a language (I was thinking of a similar solution, but wasn't 100% sure) $\endgroup$ – nikolaevra Aug 7 '17 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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