# Is the class of non regular languages is closed under complementation?

This is the question I am asked and I am currently proving it using proof by contradiction something like this:

• Let's take some language L which is non regular.
• Let's assume compliment of L i.e. $(L^c)$ is regular.
• Since we know that regular languages are closed under complementation, complementation of $(L^c)$, i.e. $(L^c)^c$ must be regular.

• Now $(L^c)^c$ is $L$ means $L$ is regular which contradicts the assumption.

• So, our assumption that $L^c$ is regular must be false.
• Hence, we can prove that $L^c$ is not regular.

Is this a correct approach to deduce?

Using same result I have to state true/false for the following two statements and support by giving proof.

• The class of non regular languages is closed under union.

• The class of non regular languages is closed under intersection.

How do I solve these two statements using the result above? Any hints would be helpful.

Thanks.

• Your proof is correct. As for the next two statements: consider a language $L$ and its complement $L^c$. What can you say about their union/intersection? – Shaull Sep 20 '13 at 7:48
• Your first approach is completely correct. For the two remaining statement, you may want to use that $(A\cap B)^c = A^c \cup B^c$. – Tpecatte Sep 20 '13 at 7:49
• For intersection, you may think of two disjoint languages... – J.-E. Pin Sep 20 '13 at 8:25
• @Timot : Not quite sure how do I go through the approach you suggested. It asks for closed under union. – rohan-patel Sep 20 '13 at 14:05
• I'll give you a hint by saying that the class of non-regular languages is not closed under union. Consider the language $\Sigma^{*}$, and think about what you showed in the first part of the question. The third part will fall out from a similar method. I personally would advise not using Timot's fact here, though it is still a useful tool to have available. – ymbirtt Sep 20 '13 at 14:35