A finite automaton is the simplest machine in computer science: a fixed set of states, an input read left to right, and a rule for moving between states on each symbol. It recognises exactly the regular languages, and it is the foundation the entire Theory of Computation is built on. The one idea students trip over is that a deterministic and a non-deterministic machine, which feel very different, have exactly the same power.
Let us build both up from the formal definition and then prove they are equivalent.
The formal definition: a 5-tuple
A deterministic finite automaton (DFA) is a 5-tuple (Q, Σ, δ, q0, F):
Q is a finite set of states.
Σ is the input alphabet.
δ is the transition function.
q0 in Q is the start state.
F, a subset of Q, is the set of accepting (final) states.
The string is accepted if, starting at q0 and following δ symbol by symbol, the machine ends in a state that is in F. Everything hinges on the shape of δ.
DFA versus NFA: the one real difference
In a DFA, δ maps Q × Σ to a single state: δ(q, a) is exactly one next state. From any state, on any symbol, there is exactly one move. No choice, no ambiguity.
In a nondeterministic finite automaton (NFA), δ maps Q × Σ to a set of states, δ: Q × Σ to 2^Q. On a symbol the machine may go to several states at once, to none, and NFAs may also take ε-transitions that move without consuming input. An NFA accepts a string if at least one path through its choices ends in an accepting state.
Aspect | DFA | NFA |
|---|---|---|
Next state on a symbol | Exactly one | A set (zero, one, or many) |
ε (empty) transitions | Not allowed | Allowed |
Acceptance | The single path ends in F | Some path ends in F |
Ease of design | Harder to build | Easier to build |
States for a language | Often more | Often fewer |
The convenience of the NFA is real: it is usually far easier to design. The surprise is that it buys no extra power.
Equivalence: NFA and DFA recognise the same languages
The central theorem of this topic: for every NFA there is a DFA that accepts exactly the same language. Both recognise precisely the class of regular languages, no more and no less. The proof is a construction, and knowing it cold is worth guaranteed marks.
The reason the equivalence holds is that a run of an NFA can only ever be in some subset of its states at once. If the NFA has n states, there are at most 2^n such subsets, a finite number, so a deterministic machine can simply track "which set of NFA states am I in" as a single DFA state. That is the whole trick, and it is what the construction below mechanises.
A worked subset (powerset) construction
Take an NFA over the alphabet {0, 1} that accepts every string ending in 01. Its states are q0 (start), q1, q2 (accepting), with transitions:
δ(q0, 0) = {q0, q1}, δ(q0, 1) = {q0}
δ(q1, 1) = {q2}
q2 has no outgoing transitions
[DIAGRAM: state diagram of the NFA. Start state q0 with a self-loop on 0 and on 1, an edge labelled 0 from q0 to q1, an edge labelled 1 from q1 to q2, and q2 drawn as a double circle for accepting.]
The subset construction builds a DFA whose states are sets of NFA states. Start from the set containing the NFA start state, {q0}, and for each input symbol take the union of the NFA moves from every state in the set.
From {q0}: on 0 to δ(q0,0) = {q0, q1}; on 1 to {q0}.
From {q0, q1}: on 0 to δ(q0,0) union δ(q1,0) = {q0, q1}; on 1 to δ(q0,1) union δ(q1,1) = {q0} union {q2} = {q0, q2}.
From {q0, q2}: on 0 to {q0, q1}; on 1 to {q0}.
Name the three reachable sets A = {q0}, B = {q0, q1}, C = {q0, q2}. A DFA state is accepting if its set contains an NFA accepting state, so C (which contains q2) is the only accepting state.
DFA state | on 0 | on 1 | Accepting? |
|---|---|---|---|
A = {q0} | B | A | No |
B = {q0, q1} | B | C | No |
C = {q0, q2} | B | A | Yes |
Read it back: you only reach the accepting state C by seeing a 0 (A to B) immediately followed by a 1 (B to C), which is exactly "ends in 01". The construction is mechanical, and in the worst case an n-state NFA can blow up to 2^n DFA states, a fact examiners test directly.
Finite automata questions in GATE, UGC NET and placements
GATE CS treats finite automata as core Theory of Computation. Expect "convert this NFA to a DFA", "how many states in the minimal DFA for this language", and "which of these strings does this automaton accept". The subset construction and the 2^n worst case are recurring. Our GATE CS exam category sequences automata with regular expressions and grammars.
UGC NET Computer Science leans on the definitions and comparisons: the 5-tuple, the DFA-versus-NFA difference, and the equivalence claim as a one-mark question. State the theorem precisely.
Placement and company tests touch this in product-based interviews, usually as "what is a DFA" or a small pattern-matching machine, since regular expressions and lexical analysis rest directly on finite automata.
KnowledgeGate's published question bank carries over one thousand Theory of Computation questions, and finite automata is its densest sub-area, so there is plenty of drill on exactly these conversions.
Practise it, do not just read it
The subset construction is a procedure, and it becomes automatic only by doing it.
Work the full topic with solved conversions on the Deterministic Finite Automata learn module.
For GATE-depth Theory of Computation across the whole syllabus, GATE Guidance by Sanchit Sir sequences automata with pushdown machines and Turing machines.
The natural next topic is regular expressions and the pumping lemma, which describe the very same regular languages these machines accept.
Learn the 5-tuple, keep the one real DFA-versus-NFA difference clear, and hand-run one full subset construction. Do that, and finite automata stops being abstract and becomes marks you can count on.
Ready to test yourself? Work through our solved finite automata (DFA and NFA) MCQs, each answered in a couple of lines, to see exactly how these ideas are examined.