epsilonNFA

An epsilon NFA (ε-NFA) is a nondeterministic finite automaton that allows epsilon transitions—transitions that can be taken without consuming an input symbol. These epsilon moves enable the machine to change states spontaneously, without reading input.

Formally, an ε-NFA is a 5-tuple (Q, Σ, δ, q0, F) where Q is a finite set of states, Σ is a finite input alphabet, δ: Q × (Σ ∪ {ε}) → P(Q) is a transition relation, q0 ∈ Q is the start state, and F ⊆ Q is the set of accepting states. The transition relation assigns to each pair (state, symbol or ε) a set of successor states. An ε-transition is a move that does not consume an input symbol.

An important concept for ε-NFAs is the ε-closure. The ε-closure of a set S of states, denoted ε-closure(S), is the set of states reachable from any state in S by a path consisting solely of ε-transitions. During processing, the automaton can move along any number of ε-transitions, and then proceed to consume input symbols.

A string w ∈ Σ* is accepted by the ε-NFA if there exists a path that starts in q0, reads w with transitions on input symbols, and ends in a state in F, allowing ε-transitions to occur before, after, or between input symbols as needed.

ε-NFAs recognize exactly the regular languages. Any ε-NFA can be converted to an equivalent DFA via an extended subset construction that uses ε-closures. The resulting DFA's states correspond to ε-closures of subsets of Q.

Applications of ε-NFAs include modeling complex regular expressions and serving as a convenient intermediate formalism in automata theory and lexical analysis.

See also: NFA, DFA, regular language, subset construction.