Union of Two Regular Languages - Theorem

Theorem

For any regular languages and, language is regular.

Proof

Since and are regular, there exist NFAs that recognize and .

Let

Construct

where

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 to denote

Let be a string from . Without loss of generality assume .

Let where

Since accepts, there exist 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


We can therefore substitute for and rewrite the above path as



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, accepts and the proof is complete.


Note: The idea drawn from this mathematical proof for constructing a machine to recognize is to create an initial state and connect it to the initial states of and using arrows.

Read more about this topic:  Union Of Two Regular Languages

Famous quotes containing the word theorem:

    “To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
    —Albert Camus (1913–1960)