# Thread: Automata Proof... Theory of Computation

1. ## Automata Proof... Theory of Computation

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?

2. I am in a class where we learned this, but my teacher didnt make us prove these properties formally. What we did was show that if we have two NFAs $\displaystyle M_1$ and $\displaystyle M_2$ which recognize the languages $\displaystyle A_1$ and $\displaystyle A_2$, respectively, then we can create a new machine $\displaystyle M_{1 \cup 2}$ which recognizes $\displaystyle A_1 \cup A_2$ by creating a new start state with an $\displaystyle \epsilon$ transition to the start states of $\displaystyle M_1$ and $\displaystyle M_2$. This way, the new machine will nondeterministically recognize $\displaystyle A_1$ or $\displaystyle A_2$. Then, since we have constructed an NFA which recognizes the language $\displaystyle M_{1 \cup 2}$, it must be regular, since NFAs are equivalent to regular expressions. I will go through my book to see how you formalize the argument. Sorry if this doesn't help.

edit: OK, so your next step should be to create a new start state $\displaystyle q_0$ and describe your new transition function $\displaystyle \delta=\{ \delta_0 , \delta_1 , \delta_2 \}$ with $\displaystyle \delta_0 \left( {q_0 , \epsilon} \right) = \{ q_1 ,q_2 \}$ and keep $\displaystyle \delta_1$ and $\displaystyle \delta_2$ the same. Then you make $\displaystyle F=\{ F_1 \cup F_2 \}$. You should also make $\displaystyle Q=\{q_0 , Q_1, Q_2 \}$. Hope this is correct and helps.

edit 2: I just saw you are working deterministically, so if you haven't learned about NFAs then this is kind of a useless post.

3. I know about NFAs and such, but this is a purely Deterministic Automaton and should be constructed strictly as a Deterministic Automaton.

But thanks, there's some useful information in there.