A regular expression describes a token language; a finite automaton recognises it — reads a string and answers yes/no. The scanner runs on automata, so the whole lexing pipeline (regex → NFA → DFA → minimised table) is a chain of automata transformations. This page pins down the two species that matter: the NFA (nondeterministic), which regexes translate into naturally, and the DFA (deterministic), which a scanner can actually execute at one step per character. They recognise exactly the same class of languages — the regular languages — and the difference between them is convenience, not power.

The formal definition: a 5-tuple

Both flavours are the same five parts; only the transition function \delta differs. A finite automaton is M = (Q, \Sigma, \delta, q_0, F):

For a DFA, \delta : Q \times \Sigma \to Q — given a state and a symbol, exactly one next state. For an NFA, \delta : Q \times (\Sigma \cup \{\varepsilon\}) \to 2^{Q} — given a state and a symbol (or the empty string \varepsilon), a set of possible next states, which may be empty. Two freedoms distinguish the NFA: it may offer several arrows on the same symbol, and it may take \varepsilon-transitions that consume no input at all.

An NFA with ε-moves

Here is a small NFA over \Sigma = \{a, b\} that accepts strings matching a^{*}b — any number of as followed by a single b — built with a free \varepsilon-jump so you can see nondeterminism in the flesh. Watch the two hallmarks of an NFA appear: an \varepsilon-edge that costs no input, and a state whose future is a set, not a point.

Faced with the string aab, the NFA cannot know in advance when to take the \varepsilon-jump from q_0 to q_1. So it explores all possibilities at once — the essence of nondeterminism. A string is accepted if some path through the machine, using any legal mix of symbol- and \varepsilon-moves, ends in an accepting state. One winning thread suffices; the failed threads are simply forgotten.

The equivalent DFA

The same language a^{*}b has a deterministic recogniser with no \varepsilon-moves and exactly one arrow leaving every state on every symbol. There is never a choice to explore: read a character, follow the one arrow, repeat. This is the machine a scanner runs.

From the start state A, an a loops back to A (still expecting the b) and a b advances to the accepting state B. From B, any further character is illegal for a^{*}b, so both symbols drop into the non-accepting dead state D, which traps forever. The dead state is the price of totality: a DFA must define every state-symbol pair, so "no legal continuation" becomes an explicit trap rather than a missing arrow.

Transition tables: the machine as data

A diagram is for humans; a transition table is for the machine. Rows are states, columns are symbols, and each cell holds the next state (a single state for a DFA, a set for an NFA). Here is the DFA above:

And the NFA — notice the cells now hold sets, an \varepsilon column appears, and some cells are empty (\varnothing, "nowhere to go"):

Simulating each machine

The two tables run differently. A DFA keeps a single current state and overwrites it each step — trivially fast. An NFA keeps a set of current states (every place a thread could be) and, on each symbol, computes the union of moves from all of them, sprinkled with \varepsilon-closures. This "set-of-states" simulation is exactly the subset construction done lazily, one input at a time. Below, a DFA simulator over the table above:

aaab accepts (three as then a b); abb rejects (it reaches B on the first b, then the second b drops it into the dead state). Because there is never a choice, the DFA touches each character exactly once — no exploring, no backtracking. That determinism is the entire reason we bother converting NFAs to DFAs for a scanner.