1
$\begingroup$

This question already has an answer here:

  • Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language.
  • But let's say if the complement of L1 is a non-regular language, is it safe to conclude that L1 is a non-regular language as well?

Since I'm trying to prove a language L1 is not a regular language, and the pumping lemma doesn't work well with this case. But I can easily prove the complement of L1 is not regular, I'm wonder if that option is possible.

$\endgroup$

marked as duplicate by Apass.Jack, xskxzr, Evil, Yuval Filmus formal-languages May 21 at 16:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.

More generally, suppose we have defined a collection of languages as myLanguages. Then

myLanguages are closed under complement $\Longleftrightarrow$ non-myLanguages are closed under complement

For example, we have

  • non-context-free languages are not closed under complement.
  • non-context-sensitive languages are closed under complement.
  • non-deterministic-context-free languages are closed under complement.
$\endgroup$

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