In a nondeterministic finite automaton (NFA), a state may have zero, one, or many outgoing arrows for the same symbol — and it may take an ε-transition that consumes no input at all.
Picture the computation as a tree of parallel possibilities. At each symbol the machine forks into every legal next state. The string is accepted if any branch ends in an accept state.
Definition · NFA
An NFA is a 5-tuple (Q, Σ, δ, q₀, F) where the transition function returns a set of states:
δ : Q × (Σ ∪ {ε}) → P(Q)Why bother?
Nondeterminism never adds computational power for finite automata, but it makes machines dramatically smaller and easier to design — a theme that returns with full force in complexity theory (P vs NP).