Union of two regular languages

In formal language theory, and in particular the theory of nondeterministic finite automata, it is known that the union of two regular languages is a regular language. This article provides a proof of that statement.

Theorem

For any regular languages $L_{1}$ and $L_{2}$ , language $L_{1} \cup L_{2}$ is regular.

Proof

Since $L_{1}$ and $L_{2}$ are regular, there exist NFAs $N_{1}, N_{2}$ that recognize $L_{1}$ and $L_{2}$ .

Let

N_{1} = (Q_{1}, Σ, T_{1}, q_{1}, A_{1})

N_{2} = (Q_{2}, Σ, T_{2}, q_{2}, A_{2})

^{[clarification needed]}

Construct

N = (Q, Σ, T, q_{0}, A_{1} \cup A_{2})

where

Q = Q_{1} \cup Q_{2} \cup {q_{0}}

T (q, x) = {\begin{matrix} T_{1} (q, x) & if & q \in Q_{1} \\ T_{2} (q, x) & if & q \in Q_{2} \\ {q_{1}, q_{2}} & if & q = q_{0} a n d x = ϵ \\ \emptyset & if & q = q_{0} a n d x \neq ϵ \end{matrix}

In the following, we shall use $p \overset{x, T}{\to} q$ to denote $q \in E (T (p, x))$ ^{[clarification needed]}

Let $w$ be a string from $L_{1} \cup L_{2}$ . Without loss of generality assume $w \in L_{1}$ .

Let $w = x_{1} x_{2} \dots x_{m}$ where $m \geq 0, x_{i} \in Σ$

Since $N_{1}$ accepts $x_{1} x_{2} \dots x_{m}$ , there exist $r_{0}, r_{1}, \dots r_{m} \in Q_{1}$ such that^{[clarification needed]}

q_{1} \overset{ϵ, T_{1}}{\to} r_{0} \overset{x_{1}, T_{1}}{\to} r_{1} \overset{x_{2}, T_{1}}{\to} r_{2} \dots r_{m - 1} \overset{x_{m}, T_{1}}{\to} r_{m}, r_{m} \in A_{1}

Since $T_{1} (q, x) = T (q, x) \forall q \in Q_{1} \forall x \in Σ$

r_{0} \in E (T_{1} (q_{1}, ϵ)) \Rightarrow r_{0} \in E (T (q_{1}, ϵ))

r_{1} \in E (T_{1} (r_{0}, x_{1})) \Rightarrow r_{1} \in E (T (r_{0}, x_{1}))

⋮

r_{m} \in E (T_{1} (r_{m - 1}, x_{m})) \Rightarrow r_{m} \in E (T (r_{m - 1}, x_{m}))

We can therefore substitute $T$ for $T_{1}$ and rewrite the above path as

$q_{1} \overset{ϵ, T}{\to} r_{0} \overset{x_{1}, T}{\to} r_{1} \overset{x_{2}, T}{\to} r_{2} \dots r_{m - 1} \overset{x_{m}, T}{\to} r_{m}, r_{m} \in A_{1} \cup A_{2}, r_{0}, r_{1}, \dots r_{m} \in Q$

Furthermore,

\begin{matrix} T (q_{0}, ϵ) = {q_{1}, q_{2}} & \Rightarrow & q_{1} \in T (q_{0}, ϵ) \\ \Rightarrow & q_{1} \in E (T (q_{0}, ϵ)) \\ \Rightarrow & q_{0} \overset{ϵ, T}{\to} q_{1} \end{matrix}

and

q_{0} \overset{ϵ, T}{\to} q_{1} \overset{ϵ, T}{\to} r_{0} \Rightarrow q_{0} \overset{ϵ, T}{\to} r_{0}

The above path can be rewritten as

q_{0} \overset{ϵ, T}{\to} r_{0} \overset{x_{1}, T}{\to} r_{1} \overset{x_{2}, T}{\to} r_{2} \dots r_{m - 1} \overset{x_{m}, T}{\to} r_{m}, r_{m} \in A_{1} \cup A_{2}, r_{0}, r_{1}, \dots r_{m} \in Q

Therefore, $N$ accepts $x_{1} x_{2} \dots x_{m}$ and the proof is complete.^{[clarification needed]}

Note: The idea drawn from this mathematical proof for constructing a machine to recognize $L_{1} \cup L_{2}$ is to create an initial state and connect it to the initial states of $L_{1}$ and $L_{2}$ using $ϵ$ arrows.

References

Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X Search this book on .. (See . Theorem 1.22, section 1.2, pg. 59.)

This article "Union of two regular languages" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Union of two regular languages. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

Union of two regular languages

Theorem

References

📰 Article(s) of the same category(ies)