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₁ and L₂, language L₁ ∪ L₂ is regular.''

Proof

Since L₁ and L₂ are regular, there exist NFA's N₁, N₂ that recognize

L₁ and L₂.

Let

N₁ = (Q₁, Σ, T₁, q₁, A₁)

N₂ = (Q₂, Σ, T₂, q₂, A₂)

Construct

N = (Q, Σ, T, q₀, A₁∪A₂)

where

Q = Q₁ ∪ Q₂ ∪ {q₀}

$$T(q,x) = \left\{\begin{array}{lll} T_{1}(q,x) & \mbox{if} & q\in Q_{1} \\ T_{2}(q,x) & \mbox{if} & q\in Q_{2} \\ \{q_{1}, q_{2}\} & \mbox{if} & q = q_{0}\ and\ x =\epsilon\\ \phi & \mbox{if} & q = q_{0}\ and\ x\neq\epsilon \end{array}\right.$$

In the following, we shall use $p\stackrel{x,T}{\rightarrow}q$ to denote q ∈ E(T(p,x))

Let w be a string from L₁ ∪ L₂

w ∈ L₁ or w ∈ L₂

Assume w ∈ L₁ (Proof would be similar if w ∈ L₂)

Let w = x₁x₂⋯x_m where m ≥ 0, x_i ∈ Σ

Since N₁ accepts x₁x₂⋯x_m, there exist r₀, r₁, ⋯r_m ∈ Q₁ such that

$$q_{1}\stackrel{\epsilon , T_{1}}{\rightarrow}r_{0}\stackrel{x_{1} , T_{1}}{\rightarrow}r_{1}\stackrel{x_{2} , T_{1}}{\rightarrow}r_{2}\cdots r_{m-1}\stackrel{x_{m} , T_{1}}{\rightarrow}r_{m}, r_{m}\in A_{1}$$

Since T₁(q,x) = T(q,x) ∀q ∈ Q₁∀x ∈ Σ

r₀ ∈ E(T₁(q₁,ϵ)) ⇒ r₀ ∈ E(T(q₁,ϵ))

r₁ ∈ E(T₁(r₀,x₁)) ⇒ r₁ ∈ E(T(r₀,x₁))

⋮

r_m ∈ E(T₁(r_m − 1,x_m)) ⇒ r_m ∈ E(T(r_m − 1,x_m))

We can therefore substitute T for T₁ and rewrite the above path as

   $q_{1}\stackrel{\epsilon , T}{\rightarrow}r_{0}\stackrel{x_{1} , T}{\rightarrow}r_{1}\stackrel{x_{2} , T}{\rightarrow}r_{2}\cdots r_{m-1}\stackrel{x_{m} , T}{\rightarrow}r_{m}, r_{m}\in A_{1}\cup A_{2}, r_{0}, r_{1},\cdots r_{m}\in Q$

Furthermore,

\begin{array}{lcl} T(q_{0}, \epsilon) = \{q_{1}, q_{2}\} & \Rightarrow & q_{1}\in T(q_{0}, \epsilon)\\

                       \\ & \Rightarrow & q_{1}\in E(T(q_{0}, \epsilon))\\
                       \\ & \Rightarrow & q_{0}\stackrel{\epsilon , T}{\rightarrow}q_{1}

\end{array}

and

$q\_\{0\}\backslash stackrel\{\backslash epsilon\; ,\; T\}\{\backslash rightarrow\}q\_\{1\}\backslash stackrel\{\backslash epsilon\; ,\; T\}\{\backslash rightarrow\}r\_\{0\}\backslash Rightarrow\; q\_\{0\}\backslash stackrel\{\backslash epsilon\; ,\; T\}\{\backslash rightarrow\}r\_\{0\}$

The above path can be rewritten as

$$q_{0}\stackrel{\epsilon , T}{\rightarrow}r_{0}\stackrel{x_{1} , T}{\rightarrow}r_{1}\stackrel{x_{2} , T}{\rightarrow}r_{2}\cdots r_{m-1}\stackrel{x_{m} , T}{\rightarrow}r_{m}, r_{m}\in A_{1}\cup A_{2}, r_{0}, r_{1},\cdots r_{m}\in Q$$

Therefore, N accepts x₁x₂⋯x_m and the proof is complete.

Note: The idea drawn from this mathematical proof for constructing

a machine to recognize L₁ ∪ L₂ is to create an initial state and connect

it to the initial states of L₁ and L₂ using ϵ arrows.

References

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