NFA with ε-Transition, ε-Closure, and Regular Expression to FA Conversion

1. NFA with ε-Transition (ε-NFA)

An NFA with ε-transition (also called ε-NFA) is a Nondeterministic Finite Automaton that allows transitions on the empty string ε (without consuming any input symbol).

Formally, an ε-NFA is defined as a 5-tuple:

M = (Q, Σ, δ, q₀, F)

where:

• Q = finite set of states
• Σ = finite input alphabet
• δ : Q × (Σ ∪ {ε}) → 2^Q = transition function (can take ε as input)
• q₀ ∈ Q = start state
• F ⊆ Q = set of final/accepting states

The key difference from a standard NFA is that the transition function accepts ε as a valid input, allowing the automaton to move from one state to another without reading any symbol.

2. ε-Closure of a State

The ε-closure of a state q is the set of all states reachable from q by following zero or more ε-transitions (including q itself).

ε-closure(q) = {p ∈ Q | p is reachable from q using only ε-transitions}

Properties:

• q is always in ε-closure(q) (reflexive)
• If p ∈ ε-closure(q) and r ∈ ε-closure(p), then r ∈ ε-closure(q) (transitive)

Example: If q --ε--> p --ε--> r, then ε-closure(q) = {q, p, r}

3. Theorem: For Every Regular Expression r, There Exists an ε-NFA Accepting L(r)

Proof by Structural Induction (Thompson's Construction Rules):

We show construction rules for each case of a regular expression.

Base Cases

Rule 1: r = ∅ (empty language)

  →[q₀]  (no transitions, no final state)

The ε-NFA has start state q₀ with no accepting states.

Rule 2: r = ε (empty string)

  →[q₀] --ε--> ((q_f))

One ε-transition from start to final state.

Rule 3: r = a (single symbol a ∈ Σ)

  →[q₀] --a--> ((q_f))

One transition on symbol a from start to final state.

Inductive Cases

Assume ε-NFAs N(r) and N(s) exist for regular expressions r and s.

Rule 4: r = r₁ | r₂ (Union / Alternation)

Create a new start state and new final state, connect with ε-transitions:

              ε --> [N(r₁)] --> ε
  →[q₀] --<                        >--> ((q_f))
              ε --> [N(r₂)] --> ε

• New start state q₀ goes to start of N(r₁) and N(r₂) via ε
• Final states of N(r₁) and N(r₂) go to new final state q_f via ε

Rule 5: r = r₁ . r₂ (Concatenation)

Connect the final state of N(r₁) to the start state of N(r₂) via ε:

  →[N(r₁)] --ε--> [N(r₂)]-->((q_f))

• Final state of N(r₁) becomes non-final
• ε-transition connects it to start of N(r₂)

Rule 6: r = r₁ (Kleene Star / Closure)*

         ε (loop back)
         ↑___________↓
  →[q₀] --ε--> [N(r₁)] --ε--> ((q_f))
      |_________________________↑
                  ε (skip, for empty string)

• New start state q₀ connects to start of N(r₁) via ε
• Final state of N(r₁) loops back to start of N(r₁) via ε
• New start state also connects directly to new final state via ε (to accept ε)

Since every regular expression is built from these base cases and operations, and we have shown an ε-NFA construction for each, by induction, every regular expression has an equivalent ε-NFA. ∎

4. Convert Regular Expression (a+b)ab to Equivalent Finite Automaton

The regular expression is: (a+b)*ab*

This means: strings over {a,b} that contain at least one 'a', ending with zero or more b's -- more precisely, any string of a's and b's, followed by 'a', followed by zero or more b's.

Step 1: Break the expression into parts

Step 2: Build ε-NFA for each part

Part 1: (a+b)*

         a
    ε ↗[q₁]↘ ε
[q₀]          [q₃] --ε--> ((q₄))
    ε ↘[q₂]↗ ε
         b

With loop: q₄ --ε--> q₀ (for the * closure), and q₀ --ε--> q₄ (for accepting zero repetitions of (a+b), i.e. the empty string). This gives the complete ε-NFA fragment for (a+b)*, with q₀ as its start state and q₄ as its accepting state.

Part 2: Single symbol a

  →[q5] --a--> ((q6))

Part 3: b*

        ε (loop back)
        ↑___________↓
  →[q7] --ε--> [q8] --b--> ((q9))
      |_____________________↑
                  ε (skip, for zero b's)

Step 3: Concatenate the Three Parts

By the concatenation rule (Rule 5 above), the accepting state of one block is joined to the start state of the next block with an ε-transition, and it stops being an accepting state in its own right (only the final block keeps an accepting state):

• q₄ --ε--> q₅ (end of the (a+b)* block feeds into the mandatory a)
• q₆ --ε--> q₇ (end of the mandatory a feeds into the b* block)

Step 4: Complete ε-NFA for (a+b)*ab*

Verification:

• On "ab": q0 --ε--> q4 (zero repetitions of (a+b)) --ε--> q5 --a--> q6 --ε--> q7 --ε--> q9 (zero b's). Accepted.
• On "aabb": q0 --ε--> q1 --a--> q3 --ε--> q0 --ε--> q4 --ε--> q5 --a--> q6 --ε--> q7 --ε--> q8 --b--> q8 --b--> q8 --ε--> q9. The symbols consumed, in order, are a (one turn of the star), a (the mandatory a), b, b (two turns of b*), i.e. exactly "aabb". Accepted.

This ε-NFA accepts precisely the language of (a+b)*ab*: any string over {a, b} (possibly empty), followed by a mandatory a, followed by zero or more b's. This completes the required conversion of the regular expression to an equivalent finite automaton via Thompson's construction.