Epsilon-NFA (ε-NFA)

Epsilon-NFA (ε-NFA)

An ε-NFA is an NFA that includes epsilon (ε) transitions — moves that change state without consuming any input symbol. These free moves add even more flexibility to the nondeterministic model, making it easier to build automata from regular expressions.

ε-transitions are like invisible doors. You can walk through them at any time, for free, without "spending" any input. This makes designing automata more intuitive, but the resulting machine still accepts the same class of languages as a DFA.

Formal Definition

An ε-NFA is a 5-tuple (Q, Σ, δ, q0, F) where δ: Q × (Σ ∪ {ε}) → P(Q). The transition function allows ε as an input symbol, meaning from any state you can move to another state without consuming input.

ε-NFA accepting "ab" or "cd":

  q0 --ε--> q1
  q0 --ε--> q3
  q1 --a--> q2
  q2 --b--> q4
  q3 --c--> q4 (typo, let's use q4 correctly)
  q3 --c--> q4
  q4 --d--> q5

  Actually, let's be precise:

  q0 --ε--> q1    (path for "ab")
  q0 --ε--> q3    (path for "cd")
  q1 --a--> q2
  q2 --b--> q5    (accept)
  q3 --c--> q4
  q4 --d--> q5    (accept)

Trace "ab":
  q0 →(ε) q1 →(a) q2 →(b) q5 ✓ Accept

Trace "cd":
  q0 →(ε) q3 →(c) q4 →(d) q5 ✓ Accept

ε-Closure

The ε-closure of a state q, written ε-closure(q), is the set of all states reachable from q using only ε transitions (including q itself). This is a critical concept for converting ε-NFA to DFA.

To compute ε-closure(q): start with {q}. For each state in the set, add all states reachable via ε transitions. Repeat until no new states are added.

Example:

  q0 --ε--> q1 --ε--> q2
  q1 --ε--> q3

  ε-closure(q0) = {q0, q1, q2, q3}
  ε-closure(q1) = {q1, q2, q3}
  ε-closure(q2) = {q2}
  ε-closure(q3) = {q3}

Converting ε-NFA to DFA

The process is similar to the subset construction, but you use ε-closure at each step. The DFA start state is ε-closure of the NFA's start state. For each DFA state (set of NFA states) and each input symbol, first compute the set of states reachable, then compute the ε-closure of that set.

Any DFA state containing an NFA accept state becomes a DFA accept state. The result is a DFA that recognizes the same language as the ε-NFA.