DFA construction

Finite automata are the simplest model of computation — a machine with a fixed, bounded amount of memory — and they sit at the heart of every grep search, every lexical analyser (like lex or flex), and every regular-expression engine. Understanding them fully, including where they fail, is the cornerstone of GATE CS Theory of Computation.

Definition: A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F): a finite set of states Q; an input alphabet Σ; a transition function δ: Q × Σ → Q mapping every (state, symbol) pair to exactly one next state; a unique start state q₀ ∈ Q; and a set of accept (final) states F ⊆ Q. The DFA accepts a string w if, after processing every symbol from q₀, it ends in a state belonging to F.

DFA in detail

The word "deterministic" means: at every moment, given the current state and the next input symbol, there is no choice — exactly one next state exists. The DFA never backtracks; it reads the input exactly once, left to right, in O(|w|) time.

A DFA rejects a string if it ends in a non-accept state, or (informally, with a stuck state / dead state) if a transition is undefined for some symbol (though a total DFA always has a transition to a dead/trap state for undefined pairs).

Worked example — DFA for binary numbers divisible by 3:

States represent remainders modulo 3: q₀ (remainder 0, also the start and sole accept state), q₁ (remainder 1), q₂ (remainder 2).

Transitions: reading a bit b from state qᵣ, the new remainder is (2r + b) mod 3.

• From q₀: on 0 → q₀; on 1 → q₁.
• From q₁: on 0 → q₂; on 1 → q₀.
• From q₂: on 0 → q₁; on 1 → q₂.

This 3-state DFA (minimal) accepts exactly the binary strings whose integer value is divisible by 3 — including the empty string (value 0). This is a classic GATE question: the answer is 3 states.

NFA — non-deterministic finite automaton

Definition: An NFA relaxes δ to δ: Q × (Σ ∪ {ε}) → 2^Q. From a given state and symbol, there may be zero, one or several possible next states. ε-transitions allow state changes without consuming any input symbol.

The NFA accepts a string if there exists at least one computation path that ends in an accept state. The NFA does not "choose wisely" — it explores all paths simultaneously (or, equivalently, it is always lucky with its choices).

Why NFAs are useful: they can be built directly from a regular expression by Thompson's construction, with one state per symbol and operator — a clean, mechanical translation. The resulting NFA may have many ε-transitions but is compact and regular-expression-faithful.

The equivalence theorem and subset construction

Key theorem: Every NFA has an equivalent DFA that accepts exactly the same language.

Subset construction: Build the DFA whose states are subsets of the NFA's state set. The start state of the DFA is the ε-closure of the NFA's start state. Each DFA state S on symbol a transitions to ε-closure(⋃_{q∈S} δ_NFA(q, a)).

Cost: the DFA may need up to 2^|Q| states — exponential in the NFA's state count. This worst case is achievable (there are known NFA families that require 2^n states in any equivalent DFA), but in practice most NFAs blow up far less dramatically.

Implication: non-determinism buys convenience and compactness, never extra computational power. NFAs and DFAs recognise exactly the same class of languages — the regular languages.

ε-NFA and regular expressions

An ε-NFA is an NFA that explicitly allows ε-transitions. The ε-closure of a state q is the set of all states reachable from q by zero or more ε-transitions (including q itself).

Regular expression → ε-NFA → DFA (the standard pipeline):

1. Parse the regex into an abstract syntax tree.
2. Thompson's construction: build an ε-NFA fragment for each atom (single character), then combine fragments using rules for concatenation, union (|) and Kleene star (*). The result is an ε-NFA with O(m) states where m = length of the regex.
3. Subset construction: convert to a DFA.
4. Minimisation (Hopcroft's algorithm, O(n log n)): merge equivalent states into a single minimal DFA.

This pipeline is exactly how grep, lex/flex and most pattern-matching engines work.

Regular languages — definition and closure

A language L is regular if and only if some DFA (equivalently, some NFA, ε-NFA, or regular expression) recognises it. The class of regular languages is denoted REG or sometimes L in GATE notation.

Closure properties: Regular languages are closed under all of the following:

• Union: L₁ ∪ L₂
• Intersection: L₁ ∩ L₂
• Complement: L̄
• Difference: L₁ \ L₂
• Concatenation: L₁L₂
• Kleene star: L*
• Reverse: L^R
• Homomorphism and inverse homomorphism

Combine any regular languages with these operations and the result is still regular. This is useful for proving a language is regular by constructing it from known regular pieces.

Decidable problems for DFAs

All standard questions about DFAs are decidable (algorithms exist and terminate):

Problem	Method	Complexity
Membership: is w ∈ L(M)?	Simulate M on w	O(|w|)
Emptiness: is L(M) = ∅?	Reachability from q₀; any accept state reachable?	O(|Q|²)
Equivalence: L(M₁) = L(M₂)?	Minimise both; compare canonical forms	Polynomial
Finiteness: is L finite?	Does the minimal DFA contain any cycle on a path from q₀ to F?	Polynomial
Minimisation	Hopcroft's algorithm	O(n log n)

The Pumping Lemma for regular languages

The Pumping Lemma is a proof tool for non-regularity. It is NOT used to prove a language IS regular — it is used to prove it is NOT.

Statement: If L is regular, then there exists a pumping length p ≥ 1 such that for every string s ∈ L with |s| ≥ p, there exists a decomposition s = xyz satisfying:

1. |xy| ≤ p
2. |y| ≥ 1
3. xy^i z ∈ L for all i ≥ 0

Intuition: A DFA with p states must repeat some state when processing any string of length ≥ p. The portion of input corresponding to the repeated state is y — a loop that can be pumped (repeated any number of times, including zero) while keeping the string in L.

To prove a language is NOT regular using the Pumping Lemma, use proof by contradiction:
Assume L is regular with pumping length p.
Choose a string s ∈ L with |s| ≥ p carefully — the choice of s is yours to optimise.
Show that for every possible split xyz (satisfying conditions 1 and 2), there exists some i where xy^i z ∉ L.
Conclude that L is not regular.

Worked example — proving { aⁿbⁿ } is not regular

Question: Show that L = { aⁿbⁿ | n ≥ 0 } is not regular.

Solution:
Step 1: Assume L is regular with pumping length p. Choose s = aᵖbᵖ. Then s ∈ L and |s| = 2p ≥ p.
Step 2: By condition (1), |xy| ≤ p, so the substring xy lies entirely within the leading block of a's. By condition (2), y consists of at least one 'a' — say y = aᵏ for some k ≥ 1.
Step 3: Consider i = 2: xy²z = a^(p+k) b^p. Since k ≥ 1, we have p+k > p, so there are more a's than b's.
Conclusion: xy²z ∉ L, contradicting condition (3). Therefore L is not regular.

Other classic non-regular languages (GATE favourites):

• { ww | w ∈ {a,b}* } — requires remembering the first half to check the second.
• { aᵖ | p is prime } — pumping changes the count, and the resulting count need not be prime.
• { aⁿ² | n ≥ 0 } — perfect-square counts cannot be maintained by a finite state machine.
• Balanced parentheses — requires counting, hence a stack (context-free, not regular).

Why it matters

The regex → NFA → DFA pipeline is the actual mechanism inside grep, lex/flex and most tokenisers. Understanding the theory tells an engineer when a problem outgrows regex — balanced brackets, nested function calls, XML — and requires a parser (pushdown automaton / context-free grammar) instead.

Real-world example: validating "balanced brackets" in a code editor — { [ ( ) ] } correctly matched — cannot be done by a pure regular expression, because counting unbounded nesting requires memory that grows with input size, which a finite automaton does not have. That is exactly why programming languages are parsed by stack-based (context-free) tools, not regex engines.

Common misconception: that NFAs are "more powerful" than DFAs because they can try multiple paths simultaneously. They are not — they recognise exactly the same class of languages. Non-determinism only makes some machines smaller or easier to design. Every NFA can be converted to a DFA (at potential exponential cost in states) for the same language.

Cover the answer, recall, then check. 12 cards on constructing DFAs for GATE.

Q1. State the 5-tuple of a DFA and the signature of its transition function.
A1. M = (Q, Σ, δ, q0, F): finite states Q, alphabet Σ, δ: Q×Σ → Q (total function), start q0∈Q, accepting F⊆Q.

Q2. For "binary strings whose value is divisible by n", how many states does the minimal DFA need?
A2. Exactly n states — one per residue class mod n. On reading bit b, new value = (2·old + b) mod n.

Q3. Minimal states for "strings over {a,b} containing the substring aba"?
A3. 4 states (track progress ε → a → ab → aba, with aba as an absorbing accept state).

Q4. Minimal states for "the k-th symbol from the RIGHT is 1" over {0,1}?
A4. 2^(k+1) states for a DFA (an NFA needs only k+2). Counting from the right forces the DFA to remember the last k symbols.

Q5. How do you build a DFA for "the k-th symbol from the LEFT is 1"?
A5. A simple chain: count k symbols, check position k, then absorb the rest. Needs only about k+3 states — left-counting is cheap.

Q6. What is a dead (trap) state and when must you add one?
A6. A non-accepting state whose every transition self-loops. Add it to make δ total when some (state,symbol) pair has no legal move.

Q7. DFA for "length ≡ r (mod m)"?
A7. m states in a cycle q0→q1→…→q(m-1)→q0 on every symbol; accept the state(s) matching r.

Q8. Minimal DFA for "at least one a AND at least one b" over {a,b}?
A8. 4 states: (none), (a only), (b only), (both = accept).

Q9. DFA accepting exactly the empty language ∅ vs. the singleton {ε}?
A9. ∅: one non-accepting trap. {ε}: start state accepting, any symbol → dead state.

Q10. Trick for "number of a's is even AND number of b's is odd" — how many states?
A10. 4 states = product of the two 2-state parity machines (2×2). Product construction.

Q11. Why can constructing a DFA for a "count exactly k" condition blow up, while "count mod k" stays small?
A11. "mod k" needs only k residue states; "exactly k" (or "≤ k / ≥ k with a bound") needs to count up to k, giving Θ(k) or more states and no cyclic reuse.

Q12. Standard recipe to design a DFA?
A12. Identify the finite information you must remember (a residue, last few symbols, a parity, a substring-match position), make that the state set, then wire δ to update it and mark accepting states.

A Deterministic Finite Automaton M = (Q, Σ, δ, q0, F) reads an input string left to right, one symbol at a time, and from each state has exactly one move per input symbol (δ: Q×Σ → Q is a total function). It accepts a string iff processing it from q0 ends in a state of F. In GATE, DFA construction questions ask you to either draw a machine or — more often — count the minimum number of states for a given language.

The design principle: remember only what you must

A DFA's state is its entire memory. The whole skill is spotting the finite piece of information the machine has to carry:

• Residue / modular counters — "divisible by n" needs n states (value mod n); "length ≡ r mod m" needs m states.
• Parity — "even number of a's" needs 2 states; combine independent conditions with the product construction (m·n states).
• Substring search — "contains aba" tracks how much of the pattern is matched so far (a KMP-like chain).
• Suffix / positional memory — "k-th symbol from the right is 1" forces remembering the last k symbols → 2^(k+1) DFA states.

Totality and dead states

Because δ must be defined for every (state, symbol) pair, incomplete diagrams need a dead (trap) state: non-accepting, self-looping on all symbols. Forgetting it is the classic beginner error.

Where DFAs sit

Class	Recognizer	Closed under complement?
Regular	DFA / NFA / regex	Yes (swap F ↔ Q∖F)
Context-free	PDA	No
Recursive	Always-halting TM	Yes
Recursively enumerable	TM	No

Complementing a DFA is trivial because it is total and deterministic — just swap accepting and non-accepting states.

Exam Tricks & Tips

• 🎯 "Divisible by n" ⇒ n states, always (value read MSB-first: new = (n·? ...) — update residue = (base·old + digit) mod n).
• 🎯 Left-counting is cheap, right-counting is exponential: "k-th from left" ≈ k+3 states; "k-th from right" = 2^(k+1) states for a DFA.
• 🎯 Multiple independent conditions ⇒ multiply the state counts via the product/cross machine.
• 🎯 Always add the dead state before counting — an "n-state" answer often silently includes it.
• 🎯 "mod" languages give cycles; "exactly/at most k" give chains — recognise which pattern the stem describes to guess the state count fast.
• ❌ Common mistake: confusing minimum states with the number of conditions — "contains aba" needs 4 states, not 3, because the accept state must absorb the rest of the string.

Expected exam pattern

1–2 marks. Typical stems: "minimum number of states in the DFA accepting L", or "which DFA accepts L". Often paired with a subtle totality/dead-state trap, or contrasted with the NFA state count for the same language.

Quick recap

State = memory. Encode the minimal finite information (residue, parity, match-position, last-k-symbols), keep δ total with a dead state, and use the product construction for combined conditions. Divisible-by-n = n states; k-th-from-right = 2^(k+1) states.

Worked Example

Problem: Construct a DFA over the alphabet {0, 1} that accepts all binary strings which, read as binary numbers (most significant bit first), are divisible by 3. Give the states, transitions, and verify it on the input 110.

Solution:
Track the remainder modulo 3 of the number read so far. Reading one more bit b appends it to the low end, which transforms the value v to 2v + b. So the new remainder is (2·current_remainder + b) mod 3.

Use three states, one per remainder: q0 (rem 0), q1 (rem 1), q2 (rem 2).
Start state: q0 (empty prefix has value 0). Accept state: q0 (remainder 0 ⇒ divisible by 3).

Transitions, computed as (2·r + b) mod 3:
q0: on 0 → (0) → q0; on 1 → (1) → q1.
q1: on 0 → (2) → q2; on 1 → (3 mod 3 = 0) → q0.
q2: on 0 → (4 mod 3 = 1) → q1; on 1 → (5 mod 3 = 2) → q2.

Verify on 110 (which is decimal 6, divisible by 3):
q0 --1--> q1 --1--> q0 --0--> q0. Ends in the accepting state q0 ⇒ accepted. ✓ (6/3 = 2.)

Answer: A 3-state DFA {q0, q1, q2} with start = accept = q0 and the transitions above accepts exactly the binary multiples of 3; it accepts 110.