Myhill–Nerode theorem
Myhill–Nerode theorem characterises regular languages by a right-invariant equivalence relation: a language is regular iff that relation has finitely many equivalence classes, and these classes give the states of the unique minimal DFA.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two or three sentences: where an engineer uses this.
The Myhill–Nerode theorem is a fundamental tool for proving that a language is regular or not, and for constructing the smallest deterministic finite automaton (DFA) that recognises a regular language. Engineers use it when minimising state machines (hardware controllers, protocol parsers) or when proving that a pattern cannot be recognised by any finite-state device.
Key ideas
Explain plainly from first principles. Bold each term where it is defined.
- Alphabet (Σ): a finite, non-empty set of symbols. Example: Σ = {0,1}.
- String (or word): a finite sequence of symbols from Σ. The set of all strings is Σ*.
- Language (L): a subset of Σ*.
- Right context: for a string x, any string z ∈ Σ* appended on the right is a right context. We consider whether xz ∈ L for all z.
- Nerode (or Myhill–Nerode) relation for L, denoted ≡_L: an equivalence relation on Σ* defined by
- bold definition: x ≡_L y iff for every z ∈ Σ* we have xz ∈ L exactly when yz ∈ L. This means x and y cannot be distinguished by any possible continuation on the right with respect to membership in L. Equivalently, each class [x] corresponds to the left quotient x^{-1}L = { z ∈ Σ* | xz ∈ L }.
- Distinguishable strings: two strings x and y are distinguishable (with respect to L) if there exists z ∈ Σ* such that xz ∈ L and yz ∉ L, or vice versa. If no such z exists they are indistinguishable.
- Index of an equivalence relation: the number of equivalence classes. If the set of classes is finite we say the relation has finite index.
- Right-invariant equivalence relation: an equivalence relation ~ on Σ* is right-invariant if for all x,y ∈ Σ* with x ~ y and for all z ∈ Σ* we have xz ~ yz. The Nerode relation ≡_L is right-invariant by definition.
Now the main theorem (state exactly as universities do):
Myhill–Nerode theorem (exact statement):
- A language L ⊆ Σ* is regular if and only if the Nerode equivalence ≡_L has finite index.
- If ≡_L has finite index, then the minimal number of states in any DFA recognising L equals the index of ≡_L.
- The minimal DFA recognising L can be constructed with one state per ≡_L-class, start state [ε], transitions [x] --a--> [xa], and accept states those classes [x] for which x ∈ L. This minimal DFA is unique up to isomorphism.
Proof sketch (the two directions) with steps universities expect:
A. If L is recognised by some DFA M with n states, then ≡_L has at most n classes.
- Let M = (Q, Σ, δ, q0, F) recognise L. For each x ∈ Σ* let δ(q0, x) be the state reached after reading x.
- If δ(q0, x) = δ(q0, y) then for every z we have δ(q0, xz) = δ(δ(q0,x), z) = δ(δ(q0,y), z) = δ(q0, yz). Hence xz ∈ L iff yz ∈ L, so x ≡_L y.
- Thus any two strings that reach the same DFA state lie in the same ≡_L-class; therefore the number of distinct ≡_L-classes is at most the number of states n.
B. If ≡_L has finite index, construct a DFA with those classes as states and show it recognises L and is minimal.
- States Q := { [x] | x ∈ Σ* } (the set of all ≡_L-classes). Start state q0 := [ε]. Accepting states F := { [x] | x ∈ L }.
- Transition function δ([x], a) := [xa]. This is well-defined because ≡_L is right-invariant: if [x] = [y] then [xa] = [ya].
- Prove by induction on |w| that δ([x], w) = [xw]. In particular δ(q0, w) = [w], so w is accepted iff [w] ∈ F iff w ∈ L.
- Since the number of classes is finite, this DFA is finite-state and recognises L.
Minimality and uniqueness:
- Any DFA recognising L must have at least one distinct state for each ≡_L-class (from part A), so our constructed DFA has the minimal possible number of states. Minimal DFA is unique up to renaming states (isomorphism): any two minimal DFAs have the same number of states and corresponding behaviour, so they can be matched.
What to draw for a typical proof/construct diagram:
- Draw one node for each equivalence class. Label each node with a short representative string (for example [ε], [0], [00]...) and mark the start state with an incoming arrow from nowhere to [ε]. Mark accept states with double circles. Draw directed edges labelled by symbols: from node [x] draw an edge labelled 'a' to node [xa]. If a class [x] = [y], merge their nodes.
Remarks and relation to other topics: the Nerode relation is a special right-invariant equivalence relation and, in general, does not coincide with the syntactic congruence of L. The syntactic congruence is a two-sided congruence (requiring indistinguishability under both left and right contexts) and refines the Nerode relation; its quotient is the syntactic monoid of L (advanced topic; you only need the DFA construction for exams).
Formulas
Each formula on its own line in backticks, then explanation.
x ≡_L y ⇔ ∀z ∈ Σ* : (xz ∈ L ⇔ yz ∈ L) — x, y, z are strings; no SI units; applies always when defining Nerode relation for language L.
δ([x], a) = [xa] — δ is the DFA transition function on classes; a ∈ Σ; used in the DFA built from ≡_L classes.
index(≡_L) = |{ [x] : x ∈ Σ* }| — the number of equivalence classes; finite ⇔ L is regular.
minimal DFA states = index(≡_L) — number of states in any minimal DFA equals index of Nerode relation.
No SI units apply for this theoretical topic.
Worked examples
Give model answers to typical long questions.
Example 1 — Even number of 1s (L = { w ∈ {0,1}* | w has even number of 1s })
- Describe ≡_L classes: Two strings are equivalent iff they have the same parity (even/odd) of number of 1s. So there are two classes: [even] and [odd]. Representative labels: [ε] (even) and [1] (odd).
- Construct DFA: states { [even], [odd] }, start = [ε] (even), accept = { [even] }. Transitions: from [even] on '1' go to [odd]; on '0' stay in [even]. From [odd] on '1' go to [even]; on '0' stay in [odd].
- Minimality: index(≡_L) = 2, so minimal DFA must have 2 states; our DFA is minimal.
Diagram instructions: draw two nodes labelled [ε] (double circle) and [1]; arrow into [ε] as start; edges: [ε] --1--> [1], [1] --1--> [ε], both have loop labelled 0.
Example 2 — Non-regular language (L = { a^n b^n | n ≥ 0 })
- Consider strings x_k = a^k for k = 0,1,2,...
- For any i ≠ j assume i < j. Choose z = a^{0} b^{i} (i copies of b). Then x_i z = a^i b^i ∈ L, but x_j z = a^j b^i ∉ L (because j > i, not equal counts). So x_i and x_j are distinguishable.
- Thus there are infinitely many pairwise distinguishable strings, so ≡_L has infinite index. By Myhill–Nerode, L is not regular.
Write this as a short exam answer: "Show x_i and x_j are distinguishable by z = b^i. Conclude infinite index, hence L non-regular." Include the logic that any DFA would need infinitely many states, impossible.
Example 3 — Language of strings ending with '01' over Σ = {0,1}
- Distinguishable suffixes can be captured by last two symbols (or shorter prefixes when length <2). Equivalence classes: [ε] (no input yet / last seen nothing), [0], [1], [01], etc. Carefully compute and merge to find 3 classes: {strings that end with 01} (accepting), {strings that end with 0 but not 01}, and a class that includes both the start ε and all strings that end with 1 but not 01 (these are indistinguishable by right contexts). Construct the minimal DFA with 3 states, transitions defined by appending symbols.
- Minimality follows since you can find distinguishing continuations for each pair of classes.
Common mistakes
- Confusing left-invariance and right-invariance. For Nerode we need right-invariance.
- When constructing DFA from classes, forgetting to prove transition is well-defined (must use right-invariance).
- Using Pumping Lemma when Myhill–Nerode is simpler (or vice versa); pick the right tool: Myhill–Nerode is often cleaner for proving non-regular by showing infinitely many distinguishable prefixes.
For your exam
Kinds of questions and what full-marks answers include:
- Definitions: define Nerode relation, right-invariant, index. Full marks expect exact logical biconditionals (⇔) and short justification.
- Prove Myhill–Nerode theorem: supply both directions A and B above, include well-definedness of transitions and minimality argument.
- Construct minimal DFA given L: identify ≡_L classes, show transitions, mark start/accept, draw diagram and argue minimality by counting classes.
- Prove non-regular: produce an infinite family of pairwise distinguishable strings (showing infinite index). Full marks expect explicit distinguishing continuations z and clear reasoning.
- Short notes: explain uniqueness up to isomorphism; mention relation to syntactic monoid (optional for higher marks).
Quick check
Three short questions.
- State the definition of x ≡_L y.
- If a DFA recognising L has 5 states, what can you say about index(≡_L)?
- For L = { a^n b^n | n ≥ 0 }, are a^2 and a^3 equivalent? Give a distinguishing continuation or explain why none exists.
Answers: 1) x ≡_L y ⇔ ∀z ∈ Σ* : (xz ∈ L ⇔ yz ∈ L); 2) index(≡_L) ≤ 5 (cannot exceed number of states); 3) Not equivalent — distinguish by z = b^2 (a^2 b^2 ∈ L, a^3 b^2 ∉ L).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?