0
$\begingroup$

Given $L_1,L_2$ which can be any regular / non-regular languages.

Let $L_1$ and $L_1-L_2$ be regular languages.

I want to know if $L_1\cap L_2$ must be regular or not.

So, I wrote $L_1-L_2=L_1\cap L_2^c$ which is regular.

From here I don't really know what to do, because $L_2^c$ can be wither regular or non-regular.

I think that I struggle to understand what the difference operations actually means.

Any hints?

Thanks!

$\endgroup$
0

1 Answer 1

0
$\begingroup$

Your first try is to express $L_1\setminus L_2$ using the intersection operation. However, we know nothing about regularity of $L_2$ in advance. In fact, $L_2$ can be irregular, say, if $L_1 = a^*$ and $L_2=\{b^{n^2}|n>0\}$ (the language $L_1\setminus L_2$ is clearly regular, since it is empty). Instead, you can try to do an inverse: express $L_1\cap L_2$ using $L_1$ and $L_1\setminus L_2$. Both these languages are regular, thus any boolean operation over them results in a regular language.

$\endgroup$

Your Answer

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

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