Formally, an automaton is a 5-tuple (Q, Σ, δ, q₀, F) where Q is a finite set of states, Σ is the input alphabet, δ is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of accept states.
The machine starts in q₀, reads each character, follows the transition for that character, and accepts if it ends in a state in F.
w is accepted if, after reading all of w starting from q₀, the machine is in some state q ∈ F. The set of all accepted strings is called the language of the automaton, written L(M).
The two main flavours of finite automaton differ in how their transition function is defined.
From every state, on every symbol, there is exactly one next state. δ: Q × Σ → Q. Simple to simulate; one active state at a time.
From a state, a symbol may lead to zero, one, or many next states. δ: Q × Σ → 2^Q. Easier to design; harder to execute directly.
| Property | DFA | NFA |
|---|---|---|
| Transitions per symbol | Exactly 1 | 0, 1 or many |
| ε-transitions allowed | No | Yes (ε-NFA) |
| Simulation cost | O(n) per symbol | O(n·|Q|) per symbol |
| Expressive power | Identical — both recognise exactly the regular languages | |
An ε-NFA allows the machine to change state without consuming any input. These free moves make NFAs far more convenient to construct — for example, when combining two automata for union or concatenation.
S by following zero or more ε-transitions. When simulating an ε-NFA we always take the ε-closure after every step.
In this tool you can write eps or ε in the alphabet and transitions fields to add epsilon moves.
Every NFA can be converted to an equivalent DFA. The idea is elegant: each DFA state represents a set of NFA states the machine could currently be in.
Algorithm sketch:
1. Start DFA state = ε-closure({q₀})
2. For each unprocessed DFA state S and each symbol a ∈ Σ, compute move(S, a) then take its ε-closure — that is the next DFA state.
3. A DFA state is accepting if any NFA state in its set is accepting.
4. Repeat until no new states appear.
n states can produce up to 2ⁿ DFA states. In practice most states are unreachable and the blowup is rarely observed.
Ready to see it live?
Build an NFA and watch subset construction run state by state — each DFA state annotated with the NFA subset it represents.