Union of two regular languages

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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},\ \Sigma ,\ T_{1},\ q_{1},\ A_{1})
 N_{2} = (Q_{2},\ \Sigma ,\ T_{2},\ q_{2},\ A_{2})[clarification needed]

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\\
											\emptyset & \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))[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}\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[clarification needed]

	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


Therefore, N accepts x_{1}x_{2}\cdots 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 \epsilon arrows.

References[edit]

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