Union of two regular languages

In formal language theory, and in particular the theory of nondeterministic finite state machines, 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 NFA's $N\_\{1\},\; N\_\{2\}$ that recognize

$L\_\{1\}$ and $L\_\{2\}$.

Let

::$N\_\{1\}\; =\; (Q\_\{1\},\; Sigma\; ,\; T\_\{1\},\; q\_\{1\},\; A\_\{1\})$

::$N\_\{2\}\; =\; (Q\_\{2\},\; Sigma\; ,\; T\_\{2\},\; q\_\{2\},\; A\_\{2\})$ Construct

:: $N\; =\; (Q,\; Sigma\; ,\; T,\; q\_\{0\},\; A\_\{1\}cup\; A\_\{2\})$ where

::$Q\; =\; Q\_\{1\}cup\; Q\_\{2\}cup\{q\_\{0\}\}$

::

In the following, we shall use $pstackrel\{x,T\}\{\; ightarrow\}q$ to denote $qin\; E(T(p,x))$

Let $w$ be a string from $L\_\{1\}cup\; L\_\{2\}$

$win\; L\_\{1\}\; or\; win\; L\_\{2\}$

Assume $win\; L\_\{1\}$ (Proof would be similar if $win\; L\_\{2\}$)

Let $w\; =\; x\_\{1\}x\_\{2\}cdots\; x\_\{m\}$ where $mgeq\; 0,\; x\_\{i\}inSigma$

Since $N\_\{1\}$ accepts $x\_\{1\}x\_\{2\}cdots\; x\_\{m\}$, there exist $r\_\{0\},\; r\_\{1\},cdots\; r\_\{m\}in\; Q\_\{1\}$ such that ::$q\_\{1\}stackrel\{epsilon\; ,\; T\_\{1\{\; ightarrow\}r\_\{0\}stackrel\{x\_\{1\}\; ,\; T\_\{1\{\; ightarrow\}r\_\{1\}stackrel\{x\_\{2\}\; ,\; T\_\{1\{\; ightarrow\}r\_\{2\}cdots\; r\_\{m-1\}stackrel\{x\_\{m\}\; ,\; T\_\{1\{\; ightarrow\}r\_\{m\},\; r\_\{m\}in\; A\_\{1\}$

Since $T\_\{1\}(q,x)\; =\; T(q,x)\; forall\; qin\; Q\_\{1\}forall\; xinSigma$

:: $r\_\{0\}in\; E(T\_\{1\}(q\_\{1\},epsilon\; ))Rightarrow\; r\_\{0\}in\; E(T(q\_\{1\},epsilon\; ))$

:: $r\_\{1\}in\; E(T\_\{1\}(r\_\{0\},x\_\{1\}\; ))Rightarrow\; r\_\{1\}in\; E(T(r\_\{0\},x\_\{1\}\; ))$

:::: $vdots$

:: $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\}stackrel\{epsilon\; ,\; T\}\{\; ightarrow\}r\_\{0\}stackrel\{x\_\{1\}\; ,\; T\}\{\; ightarrow\}r\_\{1\}stackrel\{x\_\{2\}\; ,\; T\}\{\; ightarrow\}r\_\{2\}cdots\; r\_\{m-1\}stackrel\{x\_\{m\}\; ,\; T\}\{\; ightarrow\}r\_\{m\},\; r\_\{m\}in\; A\_\{1\}cup\; A\_\{2\},\; r\_\{0\},\; r\_\{1\},cdots\; r\_\{m\}in\; Q$

Furthermore,

::

and

:: $q\_\{0\}stackrel\{epsilon\; ,\; T\}\{\; ightarrow\}q\_\{1\}stackrel\{epsilon\; ,\; T\}\{\; ightarrow\}r\_\{0\}Rightarrow\; q\_\{0\}stackrel\{epsilon\; ,\; T\}\{\; ightarrow\}r\_\{0\}$

The above path can be rewritten as

:$q\_\{0\}stackrel\{epsilon\; ,\; T\}\{\; ightarrow\}r\_\{0\}stackrel\{x\_\{1\}\; ,\; T\}\{\; ightarrow\}r\_\{1\}stackrel\{x\_\{2\}\; ,\; T\}\{\; ightarrow\}r\_\{2\}cdots\; r\_\{m-1\}stackrel\{x\_\{m\}\; ,\; T\}\{\; ightarrow\}r\_\{m\},\; r\_\{m\}in\; A\_\{1\}cup\; A\_\{2\},\; r\_\{0\},\; r\_\{1\},cdots\; r\_\{m\}in\; Q$

Therefore, $N$ accepts $x\_\{1\}x\_\{2\}cdots\; x\_\{m\}$ and the proof is complete.

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

References

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