Automata Proof... Theory of Computation

**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?