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$
2
-
$\begingroup$ What did you try to find one yourself? $\endgroup$– greybeardNov 18, 2019 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$– gnasher729Nov 18, 2019 at 9:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.