Computability and logic · existing Mathlib declaration

Myhill–Nerode Theorem

For each possible prefix x, look at exactly which suffixes y complete x to a word in the language. The language is regular exactly when only finitely many different suffix-languages arise as x varies.

regular languages
left quotients
deterministic finite automata
finite ranges
formal languages

The theorem at a glance

Myhill–Nerode theorem at a glance

A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.

A portrait theorem poster states that a language L is regular if and only if the range of L.leftQuotient is finite, above a compact diagram pairing a finite automaton with a finite family of suffix-language cards. — Mathlib's selected Myhill–Nerode endpoint: regularity is equivalent to finiteness of the range of the left-quotient function.

Formal orientation

Statement map

This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.

Original pixels inspected. The top band displays the exact regularity/finite-range equivalence, the map u ↦ L.leftQuotient u, the suffix-language definition, a brace around representative quotient cards followed by an ellipsis, and the finite range. The lower band distinctly presents the reverse construction with states = Set.range L.leftQuotient, start = L, quotient-state transitions, and the empty-word acceptance cue. The representative a/b token rows are illustrative contents, not a claim about a particular retained language. No minimal-DFA uniqueness, finite Nerode-equivalence index, pumping lemma, official staging, receipt, registry, or publication claim appears. — Regularity of L is equivalent to the range of x ↦ L.leftQuotient x being finite.

Complementary intuition

A mathematical landmark

The theorem gives a structural characterization of regular languages: finite-state recognizability is exactly finiteness of the possible residual languages after prefixes. It is a foundational bridge between automata and language semantics.

The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.

Authoritative formal type

Exact Mathlib statement

theorem Language.isRegular_iff_finite_range_leftQuotient {α : Type u} {L : Language α} : L.IsRegular ↔ (Set.range L.leftQuotient).Finite

Selected evidence declaration text

theorem Language.isRegular_iff_finite_range_leftQuotient {α : Type u} {L : Language α} : L.IsRegular ↔ (Set.range L.leftQuotient).Finite

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.

Claim boundary

No new theorem is claimed

This target indexes Mathlib's left-quotient formulation of the Myhill–Nerode theorem. For a language L, leftQuotient sends a word x to the language of suffixes y such that x ++ y ∈ L. The theorem identifies regularity of L with finiteness of the range of that function. It does not, in this declaration, assert uniqueness of a minimal DFA, state finite index of the Nerode equivalence, or derive the pumping lemma.

Proof Atlas did not originate the Myhill–Nerode theorem or Mathlib's declaration.
The selected declaration does not state uniqueness or minimality of a DFA.
The selected declaration is not phrased as finiteness of the index of the Nerode equivalence.
The selected declaration does not state or prove the pumping lemma.
The generated explanation and visuals are not proof evidence.

Provenance

Origin and evidence stay separate

Existing declaration: Language.isRegular_iff_finite_range_leftQuotient in mathlib
Relationship: The checked artifact is the upstream declaration itself
Preferred checked artifact: artifact.library.mathlib.myhill-nerode-theorem.v001
Source handling: Verified upstream reference; no mirrored source package