# (Possibly Easy) Formal Language Question

I am looking at a "practice test" for a Theory of Computation class. It was a test in a previous year.

I am asked to prove that, given L1 and L2 are regular, the union and difference are both regular.

It seems to me that for the union, since all the members of each separate set are regular, and the union consists exactly of all those members, therefore the union is regular.

And since the difference (L1-L2) is just a subset of L1, it is also regular.

This seems awfully straightforward and skips a lot of process.

Is it correct or am I missing something?

• Let me add here -- I usually just see these two things (union and difference) asserted without proof. Also, proofs for this sort of thing (at least ones I've seen) normally involve taking finite state machines for each language and combining them. That's why the way I've done it, though it seems right, seems too simple. – RCM Oct 10 '16 at 12:21
• You seem to be invoking the theorem in your proof of the theorem here. – BlueRaja - Danny Pflughoeft Oct 10 '16 at 16:13
• en.wikipedia.org/wiki/Regular_language#Closure_properties - see the references/citations there for a potential source of proof for these facts. – D.W. Oct 10 '16 at 18:02

The reasoning you give is not formal enough. For the union case, you're just restating the theorem "the union of regular sets is regular since the union of regular sets is regular"; for the difference case, your assertion "a subset of a regular language is regular" is false ($\Sigma^*$ is regular and every language is a subset of $\Sigma^*$).