1
$\begingroup$

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:

  1. If $L_2,L_3$ are regular and $L_1 \setminus L_2 = L_3$, is $L_1$ also regular?
  2. If $L_2,L_3$ are regular and $L_1 \cap \overline{L_2} = L_3$, is $L_1$ also regular?
|cite|improve this question
$\endgroup$
  • $\begingroup$ Both exercises are the same since $L_1 \setminus L_2 = L_1 \cap \overline{L_2}$. $\endgroup$ – Yuval Filmus Jun 14 at 14:13
  • 1
    $\begingroup$ Have you tried proving the claim? Have you tried finding a counterexample? $\endgroup$ – Yuval Filmus Jun 14 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 Jun 14 at 14:22
  • $\begingroup$ Hint: What if $L_2 = \Sigma^*$? $\endgroup$ – Yuval Filmus Jun 14 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 Jun 15 at 6:36
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Your answer hit LQP review. With content of comments, it is a nice hint, could you incorporate them? $\endgroup$ – Evil Jun 14 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 Jun 15 at 23:16

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.