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?
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.
You can show this fact by a quick proof by contradiction. If you are not familiar with proof by contradiction, I recommend you read up on it to understand how it works. And you should also know that regular languages are closed under complement. This means that if a language is regular, then its complement must also be regular.
Proof:
We are given that $L$ is non-regular, and we are trying to prove that $\bar{L}$ (complement of $L$) is also non-regular.
We can prove this through proof by contradiction. Let's make the assumption that $\bar{L}$ is regular. Since regular languages are closed under complement, then the complement of $\bar{L}$, that is $\bar{\bar{L}}$, must be regular. But $\bar{\bar{L}} = L$, and we know $L$ should be NOT regular. Therefore we have a contradiction. Therefore our initial assumption that $\bar{L}$ is regular is incorrect, which must mean $\bar{L}$ is non-regular.
