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?

asked Aug 29, 2016 at 12:18
$\endgroup$
2
  • 6
    $\begingroup$ Your proof is correct and probably the easiest way to go about it. $\endgroup$ Commented 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$ Commented 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)

community wiki

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.