Let $R \in REG$. Is it true that if $F\cap R \in REG$ and $F \cap \overline{R} \in REG$ then $F \in REG$?

I took $R = \Sigma^{\ast}$ and because $F\cap R \in REG$, $F$ must be regular. Is this the right approach?

  • 2
    $\begingroup$ Think carefully about the tantalisingly simple approach that you are using. What is the complement of $\Sigma^*$? And are you really able to prove that every language is regular? $\endgroup$ – Hans Hüttel Oct 31 '16 at 4:32
  • $\begingroup$ @HansHüttel, complement of all words of language is empty set. Could you give me some ideas how to solve it? $\endgroup$ – marka_17 Oct 31 '16 at 5:55
  • 1
    $\begingroup$ Here is a hint: Given any two languages $L_F$ and $L_R$, every $w \in L_F$ is either a string in $L_R$ or not a string in $L_R$. Make use of this to express $L_F$ as a union of intersections with $L_R$ and $\overline{L_R}$, $\endgroup$ – Hans Hüttel Oct 31 '16 at 6:50
  • $\begingroup$ @HansHüttel, I invented next solution : let F is non-reguler; We know that if A_1, A_2 are regular then intersection of A_1 and A_2 is also regular; Then union of intersection of F and R and intersection of F and complement of R is regular. This union is F and non-regular, but must be regular, thus contradiction. Is it right? $\endgroup$ – marka_17 Oct 31 '16 at 9:18
  • $\begingroup$ Yes, but it is a slightly roundabout line of reasoning. You do not need to assume that F is non-regular. $\endgroup$ – Hans Hüttel Oct 31 '16 at 10:19

Here's a hint. First, show that for any two sets $A, B$, that $A = (A\cap B)\cup(A\cap\overline{B})$. Then use the fact that the union of two regular languages is regular.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.