Given $L_1$ is a regular language and $L_2$ is a non-regular language. $\Longrightarrow$ then $L_1\cap L_2$ (the intersection) is non-regular OR $L_1\cup L_2$ (the union) is non-regular.
Is it true or false? Can you give an example/proof?
Asked
Active
Viewed 101 times
0
-
What have you try so far? hint assume both are regular and try some of the operations that preserve regularity. – thibo Mar 29 '21 at 16:23
-
got it! thank you! – ryden Mar 29 '21 at 16:55
1 Answers
1
Hint. Observe that $L_2 = (L_1 \cup L_2) \cap \bigl(L_1^c \cup (L_1 \cap L_2)\bigr)$.
J.-E. Pin
- 40,163
-
1Great! I think i got it! L2 is non-regular, so it can't be that both the intersection AND the union are regular, because it'll turn L2 into regular (union&intersect between regular languages), in the contrary to our assumption.
thanks:)
– ryden Mar 29 '21 at 16:55 -
1Your argument is almost complete, but don't forget to say something about $L_1^c$. By the way, if you are satisfied with the answer, the usual way to say "thanks" is to accept it. – J.-E. Pin Mar 29 '21 at 17:24
-
If $L$ is regular, then $L^c$ is regular too, for any regular language $L$. I've already proved it (not here) so i took it as obvious. and i accept your answer. – ryden Mar 30 '21 at 06:34
-
-