-2
$\begingroup$

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?

$\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
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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