4
$\begingroup$

Let $\Sigma$ be an alphabet and $L_1,L_2 \subseteq \Sigma^*$ two regular languages.

I know that $REG$ is closed under intersections of regular languages and under complementation of a regular language. My reasoning looks like this:

$L_1 \setminus L_2 = L_1 \cap \overline L_2$

Hence, we have that $REG$ is closed under set differentiation.

Have I overlooked something?

$\endgroup$
  • 5
    $\begingroup$ Your proof is correct and probably the easiest way to go about it. $\endgroup$ – 5xum Aug 29 '16 at 12:20
  • 1
    $\begingroup$ Note that your argument is not specific to regular languages: if a class of subsets of a set is closed under intersection and complementation, then it is also closed under set difference (and under union). $\endgroup$ – J.-E. Pin Sep 1 '16 at 17:46
1
$\begingroup$

Your proof is correct and probably the easiest way to go about it.

Note that your argument is not specific to regular languages: if a class of subsets of a set is closed under intersection and complementation, then it is also closed under set difference (and under union)

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