Finite automata: DFA, NFA and the idea of converting NFA to DFA

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Write a regular expression for strings over {a, b} that end in ab. from Lesson 0.2.2
• How many non-empty substrings does a string of 5 distinct symbols have? from Lesson 0.2.1
• Which phase is the first to read the characters of the program? from Lesson 0.1.3

1 · The Story

📖

The gate at Translation House

Visitors to Translation House show a badge code made of the letters a and b. Codes that end in ab belong to staff. The guard, Bhola, has a floor of numbered tiles and a rule board: “on tile p, if you read a, step to tile …; if you read b, step to …”. He starts on the start tile, reads the badge one letter at a time, steps as the board says, and opens the door only if, after the last letter, he stands on a green tile.

Bhola never looks back and never remembers anything except which tile he stands on.

The first rule board was written quickly and is unclear: on tile p, reading a, it says “stay on p or go to q”. Bhola solves it with photocopies of himself: one copy for every choice. The door opens if any copy ends on a green tile.

Mrs. Desai dislikes a crowd of clones in the doorway. She gives Bhola a card instead, listing the set of tiles his clones would occupy. With one card per possible set, the gate needs only one guard again, and the rule board has exactly one arrow per tile and letter.

2 · Predict First

🤔

The quick rule board has 3 tiles. At most how many different “sets of tiles” could appear on Bhola’s cards? Write your guess down. The answer is in the vault.

3 · Core Concept

Deterministic finite automaton (DFA)

A DFA is a 5-tuple (Q, Σ, δ, q₀, F):

• Q: finite set of states (the tiles);
• Σ: input alphabet;
• δ: Q × Σ → Q, the transition function: exactly one next state for every state and symbol;
• q₀ ∈ Q: the start state;
• F ⊆ Q: the accepting states (also called final states; the green tiles).

It reads the input left to right, one symbol per step. It accepts the string if it ends in a state of F. The language of the DFA is the set of strings it accepts.

Dead state

If some symbol should lead nowhere, a DFA sends it to a dead state that loops to itself on every symbol and is not accepting. Diagrams often leave the dead state out.

Nondeterministic finite automaton (NFA)

An NFA allows δ(q, a) to be a set of states (possibly empty), and allows ε-moves: jumps to another state without reading anything. It accepts if some sequence of choices ends in an accepting state.

NFAs are easy to build from regular expressions: each building block (symbol, |, concatenation, *) has a small standard NFA piece, and the pieces are glued with ε-moves (Thompson’s construction).

From NFA to DFA: subset construction

Every NFA can be turned into an equivalent DFA. Each DFA state is a set of NFA states (all the places the clones could be):

• The ε-closure of a set S is S plus every state reachable from S by ε-moves alone.
• DFA start state = ε-closure({start of NFA}).
• For a DFA state S and symbol a: collect every NFA state reachable from S on a, then take the ε-closure. That set is the next DFA state.
• Repeat for every new set. A set is accepting if it contains an accepting NFA state.

With n NFA states there are at most 2ⁿ DFA states; in practice far fewer are reachable.

Why the lexer cares

Phase 1 will describe each token kind by a regular expression, turn it into an NFA, convert that to a DFA, and run the DFA on the program text: fast, one step per character, never looking back. Minimizing the DFA (merging states that behave identically on every future input) makes the table smaller.

Story → compiler term

4 · Visual

NFA for (a|b)*ab: on a, state p may stay or guess “this a starts the final ab”.

The DFA obtained by subset construction: 3 reachable sets, exactly one arrow per state and symbol.

5 · Worked Examples

Example 1 Easy

Run the DFA above on abab and on abba.

Solution

abab: {p} –a→ {p,q} –b→ {p,r} –a→ {p,q} –b→ {p,r}: ends accepting, accept. abba: {p} –a→ {p,q} –b→ {p,r} –b→ {p} –a→ {p,q}: reject. Bhola, holding one card at a time, never needs to look back.

Example 2 Medium

Do the subset construction for the NFA above.

Solution

Start {p}. From {p}: a reaches p and q → {p,q}; b reaches p → {p}. From {p,q}: a → {p,q}; b → p (from p) and r (from q) → {p,r}. From {p,r}: a → {p,q}; b → {p}. No new sets appear: 3 states out of the possible 8.

Example 3 GATE

The standard ε-NFA for (a|b)*abb has 11 states. How many states does the DFA from subset construction have, and how many does the minimal DFA have?

Solution

Subset construction reaches 5 sets (call them A–E). States A and C turn out to behave identically on every future input, so the minimal DFA has 4 states. Both counts were computed by running the construction.

6 · Shortcuts

⚡

Subset construction bound: an NFA with n states gives at most 2ⁿ DFA states; build only the reachable sets, starting from the ε-closure of the start state. Valid when: converting any NFA, with or without ε-moves.

⚡

“Ends with w” over {a,b} needs a minimal DFA with |w| + 1 states when w has no repeated overlap with itself (like ab, 01, abb). Valid when: quick state-count checks; for strings like aa the count is still |w| + 1 but transitions differ.

7 · GATE Traps

⚠️

• A DFA must have exactly one move for every state and symbol (a dead state may be implied).
• An NFA accepts if any path accepts; rejection needs all paths to fail.
• The 2ⁿ bound is a maximum; the usual answer in practice is much smaller.
• ε-moves are taken without reading input; always apply ε-closure after each move.

8 · Memory Hook

🧠

DFA = one guard, one tile. NFA = a crowd of clones. Subset construction = one guard holding a card naming the crowd’s tiles.

9 · Connect the Dots

You now have the machines that recognise words. The last primer gives four ways of organising data that the compiler uses everywhere.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markMinimal DFA

How many states does the minimal DFA for “all strings over {0,1} that end in 01” have?

Numerical answer: ________

Q2MCQ1 markDFA

In a DFA, for each state and each input symbol there is:

• (A) exactly one next state
• (B) at most one next state
• (C) any number of next states
• (D) a choice made at random

Q3MSQ1 markNFA

Which are true?

• (A) Every NFA has an equivalent DFA.
• (B) An NFA may have ε-moves.
• (C) A DFA can recognise some languages no NFA can.
• (D) An NFA accepts a string if at least one path ends in an accepting state.

Q4NAT1 markSubset bound

An NFA has 4 states. What is the maximum number of states the DFA from subset construction can have?

Numerical answer: ________

Q5MCQ1 markRun

In the 3-state DFA of this lesson (start {p}), which state is reached after reading bba?

• (A) {p}
• (B) {p,q}
• (C) {p,r}
• (D) a dead state

11 · Rule Card

• DFA (Q, Σ, δ, q₀, F): one move per state and symbol; accept if the run ends in F.
• NFA: sets of next states, ε-moves; accept if some path ends in F.
• NFA ≡ DFA in power (same languages).
• Subset construction: start = ε-closure({q₀}); next = ε-closure(moves on a); at most 2ⁿ states.
• Regular expression → NFA (Thompson) → DFA → minimal DFA: the lexer’s pipeline.

12 · Concept Ledger

statestart stateaccepting (final) statetransition function δDFAdead stateNFAε-moveε-closuresubset constructionminimal DFA

13 · Answer Vault