patternMinor
Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties
Viewed 0 times
themidgeqpropertiesregularprovethatusingcomplementnot
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#4752, answer score: 9
Revisions (0)
No revisions yet.