Theorem

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

(In other words, if $\displaystyle A_1$ and $\displaystyle A_2$ are regular languages, so is $\displaystyle A_1 \cup A_2$.)

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 $\displaystyle A \cup B$:

$\displaystyle A \cup B = \{ x|x\in A \vee x\in B\}$

So:

We have $\displaystyle A_1$ which is recognized by the finite automaton $\displaystyle M_1$ and we have $\displaystyle A_2$ which is recognized by the finite automaton $\displaystyle M_2$.

Definition of a finite automaton (Deterministic):

$\displaystyle M = (Q, \Sigma , \delta , q_0, F)$ where:

$\displaystyle Q = \text{Finite set called the States}$

Meaning:

$\displaystyle Q = \{ q_0, q_1, q_2, ..., q_n\}$,

$\displaystyle \Sigma = \text{Finite set called the Alphabet}$

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

$\displaystyle \Sigma = \{ 0, 1\}$

$\displaystyle \delta = \text{The transition function}$

$\displaystyle \delta : Q \ x \ \Sigma \longrightarrow Q$

$\displaystyle q_0 = \text{The Start State}$

$\displaystyle F = \text{Set of Accept States}$

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

Proof

Here's what I've gotten so far:

Let $\displaystyle M_1$ recognize $\displaystyle A_1$, where $\displaystyle M_1 = (Q_1, \Sigma , {\delta}_1, q_1, F_1)$, and

$\displaystyle M_1$ recognize $\displaystyle A_2$, where $\displaystyle M_2 = (Q_2, \Sigma , {\delta}_2, q_2, F_2)$.

Now, I have to construct an $\displaystyle M$ to recognize $\displaystyle A_1 \cup A_2$, where $\displaystyle M = (Q, \Sigma , \delta , q_0, F)$.

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

1. $\displaystyle Q = \{ (r_1, r_2)|r_1\in Q_1 \ \wedge \ r_2\in Q_2\}$.

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 $\displaystyle M$ will be:

$\displaystyle \Sigma = {\Sigma}_1 \cup {\Sigma}_2$

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