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?


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.

  • 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 Sep 27 '12 at 2:39

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.