# Thread:

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

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?

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 $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.

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 50, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9347586035728455, "perplexity_flag": "head"}