I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises:
- If $L_2,L_3$ are regular and $L_1 \setminus L_2 = L_3$, is $L_1$ also regular?
- If $L_2,L_3$ are regular and $L_1 \cap \overline{L_2} = L_3$, is $L_1$ also regular?
-
$\begingroup$ Both exercises are the same since $L_1 \setminus L_2 = L_1 \cap \overline{L_2}$. $\endgroup$Yuval Filmus– Yuval Filmus2019年06月14日 14:13:55 +00:00Commented Jun 14, 2019 at 14:13
-
1$\begingroup$ Have you tried proving the claim? Have you tried finding a counterexample? $\endgroup$Yuval Filmus– Yuval Filmus2019年06月14日 14:14:24 +00:00Commented Jun 14, 2019 at 14:14
-
$\begingroup$ I have tried to prove the claim considering that fact that regular languages are closed under intersection and complement.So L2 is regular , (not L2) is regular.L3 is regular then the intersection on the left side should also be regular.Using the closure under intersection , L1 should be regular. $\endgroup$Sergiu Talmacel– Sergiu Talmacel2019年06月14日 14:22:39 +00:00Commented Jun 14, 2019 at 14:22
-
$\begingroup$ Hint: What if $L_2 = \Sigma^*$? $\endgroup$Yuval Filmus– Yuval Filmus2019年06月14日 19:35:33 +00:00Commented Jun 14, 2019 at 19:35
-
$\begingroup$ In this case, the intersection would be the empty set which is a regular language.So it does not matter whether L1 is regular or not.Am I right ? $\endgroup$Sergiu Talmacel– Sergiu Talmacel2019年06月15日 06:36:13 +00:00Commented Jun 15, 2019 at 6:36
1 Answer 1
When $L_2 = \Sigma^*$, then $L_3 = \emptyset$ no matter what $L_1$ is.
Let us say that a language $L$ is subset-regular if $L \cap L'$ is regular for all languages $L'$. In other words, $L$ is subset-regular if all of its subsets (including $L$ itself) are regular.
Theorem. A language is subset-regular iff it is finite.
Proof. Clearly every finite language is subset-regular. In the other direction, an infinite language has uncountably many subsets, so not all of them can be regular. $\quad\square$
We can replace $\Sigma^*$ above with the complement of any subset-regular language, that is, with any cofinite language. Moreover, due to the theorem above, only cofinite languages work: if $L$ has a non-regular (proper) subset $L'$, then $\overline{L'} \setminus \overline{L} = \overline{L'}$ isn't regular.
-
$\begingroup$ Your answer hit LQP review. With content of comments, it is a nice hint, could you incorporate them? $\endgroup$Evil– Evil2019年06月14日 19:11:40 +00:00Commented Jun 14, 2019 at 19:11
-
1$\begingroup$ The answer seems to hit the nail straight on the head. Or do you think the little details that the empty language is regular, and that there are irregular languages, need to be mentioned? $\endgroup$gnasher729– gnasher7292019年06月15日 23:16:48 +00:00Commented Jun 15, 2019 at 23:16