LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A DFA can realize at most one Nerode class per reachable state

Statement

Let $D$ be a DFA recognizing a language $L$ . If two words $u, v \in Σ^{*}$ drive $D$ from its start state to the same state, then $u \equiv_{L} v$ . Consequently, distinct Nerode classes of $L$ must reach distinct reachable states of $D$ .

Facts & Assumptions

Given: A DFA $D = (Q, Σ, δ, q_{0}, F)$ recognizing $L$ , with extended transition function $δ^{*}$ .

[L1]

By Nerode equivalence of words, to prove $u \equiv_{L} v$ it is enough to show that $u z \in L$ if and only if $v z \in L$ for every continuation $z \in Σ^{*}$ .

[L2]

By Acceptance of a word by a DFA and the recognized language, a word $w$ belongs to $L$ exactly when $δ^{*} (q_{0}, w) \in F$ .

[L3]

By The extended transition function of a DFA, $δ^{*} (s, ε) = s$ and $δ^{*} (s, x a) = δ (δ^{*} (s, x), a)$ .

Proof

technique · direct

1.1L3construct

For every state $s$ and words $x, z$ , repeated use of [L3] gives $δ^{*} (s, x z) = δ^{*} (δ^{*} (s, x), z)$ ; in particular, $δ^{*} (q_{0}, u z) = δ^{*} (δ^{*} (q_{0}, u), z)$ and $δ^{*} (q_{0}, v z) = δ^{*} (δ^{*} (q_{0}, v), z)$ .

2.1L1L2step 1.1given

If $δ^{*} (q_{0}, u) = δ^{*} (q_{0}, v)$ , then step 1.1 implies $δ^{*} (q_{0}, u z) = δ^{*} (q_{0}, v z)$ for every $z \in Σ^{*}$ . By [L2], this gives $u z \in L$ if and only if $v z \in L$ for every $z$ , so [L1] yields $u \equiv_{L} v$ .

3.1step 2.1∎

Therefore every reachable state of $D$ contains words from at most one Nerode class, and distinct Nerode classes must land in distinct reachable states.

Depends on

Used by

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)
Eric Blais, Models of Computation, 20. Nonregular Languages (standard reference, not scraped)