9
$\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$
2
  • 6
    $\begingroup$ Your proof is correct and probably the easiest way to go about it. $\endgroup$
    – 5xum
    Aug 29, 2016 at 12:20
  • 3
    $\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, 2016 at 17:46

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .