patternModerate
Why is the complement of a language that is not regular also not regular?
Viewed 0 times
whytheregularlanguagealsothatcomplementnot
Problem
In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not regular, he wrote that it follows from the fact that the second language was the complement of the first, which we had already proved was not regular.
I was wondering if anyone could explain why this is the case?
I was wondering if anyone could explain why this is the case?
Solution
Because regular langauges are closed under complementation. That is, if $L$ is regular, so is $\overline{L}$. (Exercise: prove this.)
So, suppose that $L$ is non-regular. If its complement $\overline{L}$ were regular, then $\overline{\overline{L}}=L$ would also have to be regular.
So, suppose that $L$ is non-regular. If its complement $\overline{L}$ were regular, then $\overline{\overline{L}}=L$ would also have to be regular.
Context
StackExchange Computer Science Q#49648, answer score: 12
Revisions (0)
No revisions yet.