Theorem

The class of regular languages is closed under the union operation.

(In other words, if and are regular languages, so is .)

Problem

Prove this theorem using the Proof by Construction method.

Useful Information

A regular language merely means that some finite automaton M recognizes A.

Definition of :

So:

We have which is recognized by the finite automaton and we have which is recognized by the finite automaton .

Definition of a finite automaton (Deterministic):

where:

Meaning:

,

It's all possible symbols that can be used as an input, for example, binary is:

Meaning that this set only contains the states from that the computation accepts. They are usually recognizable.

Proof

Here's what I've gotten so far:

Let recognize , where , and

recognize , where .

Now, I have to construct an to recognize , where .

I know the first step, and that's to define Q:

1. .

The Second Step is to define the language:

2. We will assume that the language is the same for both automata. If the case may be that they have separate languages, then the language for will be:

From here I have no idea what to do... Anyone know how to do this?