Could you give me an example of languages $L_1$ (regular) and $L_2$ (not regular) where $L_1 \cap L_2$ is not regular?
$\begingroup$
$\endgroup$
-
$\begingroup$ What did you try to find one yourself? $\endgroup$ – greybeard Nov 18 '19 at 6:32
-
$\begingroup$ Seriously, what have you tried? What properties would L1 have so it doesn’t turn a non-regular language into a regular one? There is an obvious L1 that will work with any non-regular language. $\endgroup$ – gnasher729 Nov 18 '19 at 9:08
$\begingroup$
$\endgroup$
Take $L_2$ to be any nonregular language, say $\{0^n 1^n: n \ge 1\}$ and let $L_1 = (0+1)^*$ be the set of all strings over the alphabet $\{0,1\}$. Then $L_2$ is a subset of $L_1$, and their intersection is $L_2$, which is nonregular.
$\begingroup$
$\endgroup$
Suppose $\Sigma = \{a\}$. A straighforward example is $L_1= a^*$, $L_2 = \{a^p| \text{p is prime}\}$. So, $L_2 \cap L_1 = L_2$ and it is not regular.
