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?

  • $\begingroup$ 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. $\endgroup$ – RCM Oct 10 '16 at 12:21
  • $\begingroup$ You seem to be invoking the theorem in your proof of the theorem here. $\endgroup$ – BlueRaja - Danny Pflughoeft Oct 10 '16 at 16:13
  • $\begingroup$ en.wikipedia.org/wiki/Regular_language#Closure_properties - see the references/citations there for a potential source of proof for these facts. $\endgroup$ – 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^*$).

Regular languages are defined in terms of finite automata. The general approach to a proof is that you look at the definitions of what is given (L1 and L2 are regular, so there are automata...) and show a logical reasoning from that to the definition of what you want to prove (there is an automaton ... therefore L3 is regular).

| cite | improve this answer | |
  • 1
    $\begingroup$ lol. i figured i couldn't have it that easy, but saving some time in the exam would be valuable. thanks especially for the second one, since it's one thing to be insufficiently formal, but much worse to also be wrong. guess i'll have to do it the "long way." $\endgroup$ – RCM Oct 10 '16 at 13:38

Your question is based on a category error. You say "all the members of each separate set are regular" but that statement doesn't make sense. The members of the sets L1 and L2 are strings but regularity is a property of languages.

| cite | improve this answer | |

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.