# If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular?

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?

• 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? – Hans Hüttel Oct 31 '16 at 4:32
• @HansHüttel, complement of all words of language is empty set. Could you give me some ideas how to solve it? – marka_17 Oct 31 '16 at 5:55
• 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}$, – Hans Hüttel Oct 31 '16 at 6:50
• @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? – marka_17 Oct 31 '16 at 9:18
• Yes, but it is a slightly roundabout line of reasoning. You do not need to assume that F is non-regular. – 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.