Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):

  1. A language L ⊆ Σ* is regular if and only if the Nerode equivalence ≡_L has finite index.
  2. If ≡_L has finite index, then the minimal number of states in any DFA recognising L equals the index of ≡_L.
  3. 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 })

  1. 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).
  2. 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].
  3. 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 })

  1. Consider strings x_k = a^k for k = 0,1,2,...
  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.
  3. 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}

  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.
  2. 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.

  1. State the definition of x ≡_L y.
  2. If a DFA recognising L has 5 states, what can you say about index(≡_L)?
  3. 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?