Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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!
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.
