2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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? $\endgroup$
    – Shaull
    Commented Sep 20, 2013 at 7:48
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Tpecatte
    Commented Sep 20, 2013 at 7:49
  • $\begingroup$ For intersection, you may think of two disjoint languages... $\endgroup$
    – J.-E. Pin
    Commented Sep 20, 2013 at 8:25
  • $\begingroup$ @Timot : Not quite sure how do I go through the approach you suggested. It asks for closed under union. $\endgroup$
    – rohan-patel
    Commented Sep 20, 2013 at 14:05
  • $\begingroup$ 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. $\endgroup$
    – ymbirtt
    Commented Sep 20, 2013 at 14:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.