-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$
2
  • $\begingroup$ What did you try to find one yourself? $\endgroup$
    – greybeard
    Nov 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$
    – gnasher729
    Nov 18, 2019 at 9:08

2 Answers 2

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$
0
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.