SLD resolution

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,\mathrm{\Sigma },T_1,q_1,A_1)$

$N_2=(Q_2,\mathrm{\Sigma },T_2,q_2,A_2)$

Construct

$N=(Q,\mathrm{\Sigma },T,q_0,A_1\cup A_2)$

where

$Q=Q_1\cup Q_2\cup \{q_0\}$

$T(q,x)=\{\begin{array}{lll}{T}_1(q,x)& \text{if}& q\in Q_1\\ T_2(q,x)& \text{if}& q\in Q_2\\ \{q_1,q_2\}& \text{if}& q=q_{0}andx=ϵ\\ \mathrm{\varnothing }& \text{if}& q=q_{0}andx\ne ϵ\end{array}$

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

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\ge 0,x_i\in \mathrm{\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{ϵ,T_1}{\to }{r}_0\stackrel{x_1,T_1}{\to }{r}_1\stackrel{x_2,T_1}{\to }{r}_2\cdots r_{m-1}\stackrel{x_m,T_1}{\to }{r}_m,r_m\in A_1$

Since $T_1(q,x)=T(q,x)\mathrm{\forall }q\in Q_1\mathrm{\forall }x\in \mathrm{\Sigma }$

$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\stackrel{ϵ,T}{\to }{r}_0\stackrel{x_1,T}{\to }{r}_1\stackrel{x_2,T}{\to }{r}_2\cdots r_{m-1}\stackrel{x_m,T}{\to }{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,ϵ)=\{q_1,q_2\}& \Rightarrow & q_1\in T(q_0,ϵ)\\ \\ & \Rightarrow & q_1\in E(T(q_0,ϵ))\\ \\ & \Rightarrow & q_0\stackrel{ϵ,T}{\to }{q}_1\end{array}$

and

$q_0\stackrel{ϵ,T}{\to }{q}_1\stackrel{ϵ,T}{\to }{r}_0\Rightarrow q_0\stackrel{ϵ,T}{\to }{r}_0$

The above path can be rewritten as

$q_0\stackrel{ϵ,T}{\to }{r}_0\stackrel{x_1,T}{\to }{r}_1\stackrel{x_2,T}{\to }{r}_2\cdots r_{m-1}\stackrel{x_m,T}{\to }{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 $ϵ$ arrows.

References

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