a nondeterministic finite automaton

A deterministic finite automaton (DFA) is like a vending machine that, in each state, has exactly one response to each coin you insert — push a button and exactly one thing happens. A nondeterministic finite automaton (NFA) loosens this: in a given state, reading a given symbol, the machine may have several allowed next states, or none. It is the finite automaton with the power of "guessing" built in, and it accepts a string if SOME legal sequence of choices leads to an accept state.

Formally an NFA is a five-tuple (Q, Σ, δ, q0, F): a finite set of states Q; an input alphabet Σ (Sigma); a transition function δ (delta) that, given a state and a symbol, returns a SET of states (a subset of Q) rather than a single state; a start state q0; and a set of accept states F. The key difference from a DFA is the output type of δ: instead of δ(q, a) = p (one state), an NFA has δ(q, a) = a set such as {p, r} — possibly empty, possibly several. Many definitions also allow epsilon-moves, which change state while reading no symbol.

Why bother? Because NFAs are often dramatically smaller and easier to design than the equivalent DFA, while recognizing exactly the same family of languages — the regular languages. They are not more powerful (every NFA can be converted into a DFA by the subset construction). The payoff is purely conciseness and clarity of design: you describe what to look for, and let the "guessing" sort out the bookkeeping.