12
$\begingroup$

I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties.

I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a regular language. I also understand regular languages are closed under complement operation. However, does that also imply that a non-regular language's complement is also non-regular?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

Yes. Since the complement of a regular language is also a regular language, then it follows that the complement of a non-regular language must also be non-regular. Strictly speaking, this works since the complement is its own inverse.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Just to explicitly state it, the proof would run along these lines: Towards a contradiction, let L be the complement of the given language. If L were regular then the complement of L, which is the given language: $\{0^n 1^n \mid n \geq 0\}$, would be regular as well by the property of regular languages being closed over the compliment operation. Therefore L is not regular. $\endgroup$
    – JustAnotherSoul
    Commented Sep 27, 2012 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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