Automata Proof... Theory of Computation

**Aryth** · April 8th 2008, 06:21 PM

Theorem

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

(In other words, if $A_1$ and $A_2$ are regular languages, so is $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 $A \cup B$ :

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

So:

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

Definition of a finite automaton (Deterministic):

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

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

Meaning:

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

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

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

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

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

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

$q_0 = \text{The Start State}$

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

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

Proof

Here's what I've gotten so far:

Let $M_1$ recognize $A_1$ , where $M_1 = (Q_1, \Sigma , {\delta}_1, q_1, F_1)$ , and
$M_1$ recognize $A_2$ , where $M_2 = (Q_2, \Sigma , {\delta}_2, q_2, F_2)$ .

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

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

1. $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 $M$ will be:

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

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

**xifentoozlerix** · April 12th 2008, 02:01 PM

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 $M_1$ and $M_2$ which recognize the languages $A_1$ and $A_2$ , respectively, then we can create a new machine $M_{1 \cup 2}$ which recognizes $A_1 \cup A_2$ by creating a new start state with an $\epsilon$ transition to the start states of $M_1$ and $M_2$ . This way, the new machine will nondeterministically recognize $A_1$ or $A_2$ . Then, since we have constructed an NFA which recognizes the language $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 $q_0$ and describe your new transition function $\delta=\{ \delta_0 , \delta_1 , \delta_2 \}$ with $\delta_0 \left( {q_0 , \epsilon} \right) = \{ q_1 ,q_2 \}<br />$ and keep $\delta_1$ and $\delta_2$ the same. Then you make $F=\{ F_1 \cup F_2 \}$ . You should also make $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.

**Aryth** · April 12th 2008, 11:25 PM

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.

Thread: Automata Proof... Theory of Computation

LinkBack

Thread Tools

Display

Automata Proof... Theory of Computation

Similar Math Help Forum Discussions

Automata

Regular Expression (Theory of Automata)

Radon Nikodym computation, step of a proof

Help in Theory of Automata

Problems relating Theory of Automata (Computer Theory)

Search Tags