Problem Detail: 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?
Asked By : RCM
Answered By : Tom van der Zanden
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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/64440
