Union of two regular languages

From Wikipedia, the free encyclopedia

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.

[edit] 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}\}$

$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\in E(T(p,x))$

Let $w$ be a string from $L_{1}\cup L_{2}$

$w\in L_{1}\ or\ w\in L_{2}$

Assume $w\in L_{1}$ (Proof would be similar if $w\in L_{2}$ )

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

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}}{\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_{1}(q,x) = T(q,x)\ \forall q\in Q_{1}\forall x\in\Sigma$

$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}{\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}\stackrel{\epsilon , T}{\rightarrow}q_{1}\stackrel{\epsilon , T}{\rightarrow}r_{0}\Rightarrow q_{0}\stackrel{\epsilon , T}{\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$