Proof of NFA theorem

Question

Proof the theorem that the class of regular languages is closed under union; that is, if L₁ is recognized by a NFA and L₂ is recognized by a NFA, then L₁ υ L₂ is recognized by a NFA as well.

 

Answer 1

Proof:

Suppose L₁ is recognized by NFA A₁ = (Q₁;Σ; _δ1; q₁; F₁) and L₂ is recognized by NFA A₂ = (Q₂; Σ; δ₂; q₂; F₂).

Construct the NFA A = (Q; Σ; δ; q₀; F) where:

Q = Q₁ υ Q2 υ {q₀} where q₀ is not in Q₁ or Q₂.
F = F₁  υ F₂
δ  is dened as:

- (q₀; ε ) = {q₁; q₂},
- (q₀; a) = {} for a ≠ ε
- (q; a) = δ₁(q; a) for a in Σ υ {ε} and q in Q₁
- (q; a) = δ₂(q; a) for a in Σ υ {ε} and q in Q₂

Note: The construction above is nothing but the formal denition of the construction given in the slides for closure of NFAs under union!

We claim that A accepts exactly L₁ υ L₂. We need to show two directions:
if a string is in L₁ υ L₂ it is accepted by A, and if a string is accepted by A it is in L₁ υ L₂.

Throughout this argument, we refer to the formal denition of what it means for an NFA to accept, as given in the slides and on page 54 of Sipser.

First, suppose a string ω is accepted by A. Let ω' be a rewriting of ω, with ε's possibly in between letters, and r_0.... r_n for some n ≥ 0 a sequence of states such that ω' and r₀.....r_n witness acceptance according to the formal denition of acceptance of an NFA. Then r₀ = q₀, by the denition of acceptance. Since q₀ is not an accepting state of A, we must have n > 0, so there is an r₁ with r₁ ≡ δ₂ (q₀; ω'). But by the denition of A, ω' must be either q₁ or q₂, since there is only one transition out of q₀ that can lead to an accepting state.