if $\ L_{1} \cup L_{2}$ is regular and $\ L_{1} \cap L_{2}$ is regular, and $\ L_{2}$ is regular, so $\ L_{1}$ is regular.

Question

True / False:

if $\ L_{1} \cup L_{2}$ is regular and $\ L_{1} \cap L_{2}$ is regular, and $\ L_{2}$ is regular, so $\ L_{1}$ is regular.

My intuition: I assume is false, but couldn't find a counter example. My intuition comes from the fact that:

If $\displaystyle L_{2} ,\ L_{3} ,\ L_{4}$ are regular, so that: $\displaystyle L_{1} \cup L_{2} =\ L_{3}$ and $\displaystyle L_{1} \cap L_{2} =\ L_{4}$, then $\displaystyle L_{1} \ =\ L_{3} \backslash L_{2} \cup L_{4}$. Which I guess would be regular if $\displaystyle L_{3} \backslash L_{2}$ is regular. But I never heard of such a theorem, so I guess that is not the case.

Does anyone have a counter example? Or proof?

Answer 1

The class of regular languages is closed under union and relative complement, so

$$L_1=\big((L_1\cup L_2)\setminus L_2\big)\cup(L_1\cap L_2)$$

is regular.