Union of two regular languages

Theorem

For any regular languages L 1 and L 2 , language L 1 ∪ 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

Construct

where

In the following, we shall use p → x , T q to denote q ∈ E ( T ( p , x ) )

Let w be a string from L 1 ∪ L 2 . Without loss of generality assume w ∈ L 1 .

Let w = x 1 x 2 ⋯ x m where m ≥ 0 , x i ∈ Σ

Since N 1 accepts x 1 x 2 ⋯ x m , there exist r 0 , r 1 , ⋯ r m ∈ Q 1 such that

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

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

q 1 → ϵ , T r 0 → x 1 , T r 1 → x 2 , T r 2 ⋯ r m − 1 → x m , T r m , r m ∈ A 1 ∪ A 2 , r 0 , r 1 , ⋯ r m ∈ Q

Furthermore,

and

The above path can be rewritten as

Therefore, N accepts x 1 x 2 ⋯ x m and the proof is complete.

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