1
$\begingroup$
  • 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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$

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