WikiLean · Articles Articles Brain Contribute About

Preliminary: these links have not yet had an independent audit.

Nondeterministic finite automaton

88 passages34 formalized14 partial40 not formalized

Statement only

More ways to filter
Library
About this page

This page

  • Wikipedia revision 1366106761, pinned: the text here is that revision, not today's article.
  • WikiProject Mathematics: B-class, High importance
  • Annotated article on WikiLean.
  • 88 passages checked, 66 Lean locations (and 40 related declarations).

Central statements: 33 of the 88 passages state the article's subject or a named result or definition; the other 55 are supporting (examples, setup). Of these 33: 16 formalized, 10 partial, 7 not formalized.

What the colours mean

  • Formalized a Lean declaration states it, proved, or a Lean definition defines it
  • Statement only Lean states it, but the proof is not finished
  • Partial Lean states part of it, or a more general or special form
  • Not formalized searched every library and not found

Libraries searched

Searched 48 Lean libraries, pinned 2026-10-17, 3 left out (library set u1).

How these links were made

  • Accuracy, from an audit of a sample of 224 items (blind, not independent): Strong links (exact, close or broad match) on supporting passages that have exactly the right relation: 92% (95% interval 49–99%), from 36 drawn of 1029, weighted by relation and library, an effective sample of 5.1; Links in a counting relation (exact, close, broad, narrow match or part) on supporting passages that have exactly the right relation: 73% (95% interval 40–92%), from 48 drawn of 1740, weighted by relation and library, an effective sample of 8.1; Central and subject passages whose formalization status is right: 86% (95% interval 73–94%), from 44 drawn of 1905, weighted by recorded status, an effective sample of 42; 'Not formalized' on supporting passages that is right (no declaration in the 48 libraries states it): 60% (95% interval 25–87%), from 12 drawn of 1236, weighted by article, an effective sample of 6.1.
  • Audit run tierA-batch1-audit, run by jack, 2 Nov 2026, 21:10 – 3 Nov 2026, 02:10 UTC: judged by Claude Opus 5.5 (claude-opus-5-5).
  • Record set tierA-b1b (cf-locate-recordset/2, statuses by status rule 3), exported 1 Nov 2026 by formal-companion at commit d85385a.
  • Seal sha256 23710337d053e8212378a9e580805628bcdfda61a6fc431e65f24a4a16c9e602.
  • Inventory run inv-tierA-b1r, run by jack, 30 Oct 2026, 07:23–20:00 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5). It listed the formal passages, each with its kind and prominence, that the locate run then searched.
  • Locate run loc-tierA-b1b, run by jack, 31 Oct 2026, 04:59 – 1 Nov 2026, 03:06 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5).
  • Challenge run chal-tierA-b1, run by jack, 1 Nov 2026, 03:19–14:25 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5). In this article it re-checked every Lean location and absence on a central or subject passage (36 locations and 7 absences); on supporting passages, a seeded sample (seed 0; drawn at 0.5 for strong matches, 0.2 for weaker links and 0.25 for absences): 24 of 30 locations and 10 of 33 absences. In all, 60 of 66 Lean locations (91%) and 17 of 40 absences (43%) were re-checked.
  • Passage text: 88 of 88 passages shown in full, each the slice of the pinned revision's text that its record's span sha256 hashes, checked when the store was built.
  • Lean code: each declaration's type, from the declaration corpus of universe u1 (built 18 Oct 2026, sha256 a364fd6aede5), at the commit its card links.

How the text is shown

Each passage is shown in full, as revision 1366106761 states it (checked against its record's span hash when the store was built). Where a passage is only part of a sentence, it is highlighted and the rest of the sentence is shown in grey around it, from the same copy of the revision; a list item also shows the sentence that introduces it. Formulas are drawn from their TeX; hover one to see it.

Each card's Lean code is its declaration's type as Lean prints it, from the declaration corpus of library set u1 at the card's commit, laid out as a header: binders before the colon, then the hypotheses as arrows (the corpus keeps no hypothesis names) and the conclusion, in Mathlib's notation (𝓝, π, R[X], Type*). It is not the source text; Source opens that.

Passages

What “exact match”, “more general” and the other labels mean
  1. Definition · main statement

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
    each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition.

    Show in article · Read it in context on Wikipedia

    DFA more general

    structure DFA : Type u → Type v → Type (max u v)

    Mathlib.Computability.DFA · lines 59–65

    Why more general: Mathlib bundles a state type, a transition taking a state and a symbol to a single state, one start state and a set of accepting states; because the transition is a total function into the state type, determinism and symbol-consuming steps both hold by construction, while the state type may be any type.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key b40e59066bdf · pair key bfcc9380737c.
  2. Definition · Subject of the article

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions.

    Show in article · Read it in context on Wikipedia

    εNFA more general

    structure εNFA : Type u → Type v → Type (max u v)

    Mathlib.Computability.EpsilonNFA · lines 40–48

    Why more general: The structure's docstring says the state type may be infinite and that a step labelled by the empty option reads no symbol; those are exactly the two freedoms the article grants over a deterministic machine.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 07ee59030fac · pair key 1d4d8485537f.

    NFA special case

    structure NFA : Type u → Type v → Type (max u v)

    Mathlib.Computability.NFA · lines 55–61

    Why a special case: Mathlib keeps symbol-free steps in a separate structure, so this one covers the article's machines whose every transition consumes a symbol, with the state type unconstrained.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 4844354565b1 · pair key c0763476f937.
  3. Theorem · main statement

    Formalized

    Formalized: Mathlib states a more general result (proved).

    In particular, every DFA is also an NFA.

    Show in article · Read it in context on Wikipedia

    DFA.toNFA_correct more general

    theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 348–354

    Why more general: Mathlib keeps the two kinds of machine as separate structures and writes the inclusion as a construction that keeps the start and accepting states and makes each step a one-element set, together with this equality of accepted languages; the state type is arbitrary.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 231389233d4f · pair key 15a7f93bcf04.
  4. Theorem · main statement

    Formalized

    Formalized: Mathlib states a more general result (proved).

    Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language.[1]

    Show in article · Read it in context on Wikipedia

    NFA.toDFA_correct more general

    theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 312–315

    Why more general: The deterministic machine here is the one whose states are sets of the original states, built by the construction the article names, and the theorem equates the two accepted languages for every state type.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 558f17435434 · pair key 4c316308015d.
  5. Theorem · main statement

    Partial

    Partial: Mathlib states a special case (proved).

    Like DFAs, NFAs only recognize regular languages.

    Show in article · Read it in context on Wikipedia

    Language.isRegular_iff special case

    theorem Language.isRegular_iff {T : Type u} {L : Language T} : L.IsRegular ↔ ∃ σ x M, M.accepts = L

    Mathlib.Computability.DFA · lines 372–374

    Why a special case: Mathlib fixes regularity by the existence of a finite deterministic machine, so this equivalence delivers the article's conclusion exactly for the deterministic automata among its machines; the nondeterministic ones are not reached by it alone.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 2522f4a452d5 · pair key 9e7ef2bd906b.
  6. Theorem · supporting

    Not formalized
    Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton).

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt 8dd58405e51c).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  7. Definition · main statement · Informal introduction

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    If there exists at least one "lucky run", i.e. some sequence of choices leading to an accepting state after completely consuming the input, it is accepted.

    Show in article · Read it in context on Wikipedia

    NFA.accepts_iff_exists_path more general

    theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)

    Mathlib.Computability.NFA · lines 298–301

    Why more general: A run in Mathlib is an inductive path labelled by the word, so a path from a start state to an accepting state is one sequence of applicable transitions that consumes the whole word; the state type is left arbitrary.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 552c52534a46 · pair key f9ba6cbb2d43.

    NFA.accepts more general

    def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α

    Mathlib.Computability.NFA · line 253

    Why more general: This is the object the article's sentence defines: the language of words leading the machine, under some choice of transitions, into an accepting state; Mathlib states it for any state type.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key e186a1d48bce · pair key a1c8a7b5ac08.
  8. Definition · supporting · Informal introduction

    Partial

    Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.

    Otherwise, i.e. if no choice sequence at all can consume all the input[3] and lead to an accepting state, the input is rejected.

    Show in article · Read it in context on Wikipedia

    NFA.accepts_iff_exists_path more general

    theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)

    Mathlib.Computability.NFA · lines 298–301

    Why more general: Mathlib has no separate name for a refused input: it is simply a word outside the accepted language, and this equivalence read negatively is the article's condition that no choice sequence works.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 80a4bf35d156 · pair key b48003ed3f05.

    NFA.mem_accepts more general

    theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x

    Mathlib.Computability.NFA · lines 255–256

    Why more general: The same criterion through step-by-step evaluation: the set of states reachable after the whole word meets the accepting states, whose failure is the article's refusal of the input.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key ca639a37f435 · pair key f8589b155207.
  9. Definition · supporting · Informal introduction

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected.

    Show in article · Read it in context on Wikipedia

    NFA.mem_accepts more general

    theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x

    Mathlib.Computability.NFA · lines 255–256

    Why more general: Mathlib's set of states reached after the input is the collection of copies still alive in the cloning picture, and the lemma is stated for machines with a whole set of start states.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 11c97cb253d4 · pair key 247d36f6476f.

    NFA.accepts more general

    def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α

    Mathlib.Computability.NFA · line 253

    Why more general: This is the defined object: the language whose members are the inputs with an accepting state among those reached, over arbitrary state and letter types.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key feec548378f0 · pair key 072524b8d139.
  10. Definition · main statement · Formal definition › Automaton

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    An NFA is represented formally by a 5-tuple, (Q, Σ, δ, q0, F), consisting of
    a finite set of states Q, a finite set of input symbols called the alphabet Σ, a transition function δ: Q × Σ → 𝒫(Q), an initial (or start) state q0 ∈ Q, and a set of accepting (or final) states F ⊆ Q.

    Show in article · Read it in context on Wikipedia

    NFA more general

    structure NFA : Type u → Type v → Type (max u v)

    Mathlib.Computability.NFA · lines 55–61

    Why more general: Mathlib leaves the state and letter types unrestricted where the article asks for finite ones, and carries a whole set of start states where the article distinguishes one element, so it is inhabited by more machines than the article defines.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key ca57f84f9396 · pair key 5b276120706b.
  11. Notation · supporting · Formal definition › Automaton

    Formalized

    Formalized: Mathlib states this up to a convention difference (a definition).

    Here, 𝒫(Q) denotes the power set of Q.

    Show in article · Read it in context on Wikipedia

    Finset.powerset close match

    def Finset.powerset {α : Type*} : Finset α → Finset (Finset α)

    Mathlib.Data.Finset.Powerset · lines 31–33

    Why close, not exact: Mathlib carries the finite state set and each of its subsets as finite-set terms rather than as sets of states.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 76c145a017aa · pair key 2acf650a636b.

    Set.powerset more general

    def Set.powerset {α : Type u} : Set α → Set (Set α)

    Mathlib.Data.Set.Defs · line 255

    Why more general: Mathlib gives the power set of an arbitrary set, including infinite ones, where the passage names it for the finite state set of an automaton.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 072c3735dabc · pair key 95ae98f3860b.
  12. Definition · main statement · Formal definition › Recognized language

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    Given an NFA M = (Q, Σ, δ, q0, F), its recognized language is denoted by L(M), and is defined as the set of all strings over the alphabet Σ that are accepted by M.

    Show in article · Read it in context on Wikipedia

    NFA.accepts more general

    def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α

    Mathlib.Computability.NFA · line 253

    Why more general: Mathlib returns the accepted language of a machine whose carriers may be infinite and whose start states form a set, where the passage fixes a finite machine with one start state.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 3b3d8305b263 · pair key 70b627f9578d.
  13. Definition · main statement · Formal definition › Recognized language

    Partial

    Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.

    Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string w = a1a2...an being accepted by M:
    w is accepted if a sequence of states, r0, r1, ..., rn, exists in Q such that: r0 = q0 ri + 1 ∈ δ(ri, ai + 1), for i = 0, …, n − 1 rn ∈ F.

    Show in article · Read it in context on Wikipedia

    NFA.accepts_iff_exists_path more general

    theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)

    Mathlib.Computability.NFA · lines 298–301

    Why more general: Mathlib packages the run as an inductive family of paths rather than as an indexed list of states, and allows several start states where the passage has one.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 55fe71a5108b · pair key ad672c44db1a.

    NFA.Path states part

    inductive NFA.Path {α : Type u} {σ : Type v} : NFA α σ → σ → σ → List α → Type (max u v)

    Mathlib.Computability.NFA · lines 269–272

    Why only part: Mathlib carries the run as data indexed by its endpoints and its word, rather than as a list of states indexed by position.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 2e34161e56ab · pair key 14d64ca91fba.
  14. Theorem · supporting · Formal definition › Recognized language

    Formalized

    Formalized: Mathlib states a more general result (proved).

    In order for w to be accepted by M, it is not required that every state sequence ends in an accepting state, it is sufficient if one does.

    Show in article · Read it in context on Wikipedia

    NFA.accepts_iff_exists_path more general

    theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)

    Mathlib.Computability.NFA · lines 298–301

    Why more general: Mathlib proves the full equivalence, whose right-to-left half is the sufficiency the passage asserts, and it holds for machines with a set of start states.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key b736c8118a79 · pair key b31acd2aa929.
  15. Definition · supporting · Formal definition › Recognized language

    Partial

    Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.

    Otherwise, i.e. if it is impossible at all to get from q0 to a state from F by following w, it is said that the automaton rejects the string.

    Show in article · Read it in context on Wikipedia

    NFA.accepts_iff_exists_path more general

    theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)

    Mathlib.Computability.NFA · lines 298–301

    Why more general: Mathlib has no separate predicate for rejection: a rejected word is one outside the machine's accepted language, and the lemma is stated for machines with a set of start states.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 91835f79dc65 · pair key 25c991217ad4.
  16. Definition · supporting · Formal definition › Recognized language

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    The set of strings M accepts is the language recognized by M and this language is denoted by L(M).

    Show in article · Read it in context on Wikipedia

    NFA.accepts more general

    def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α

    Mathlib.Computability.NFA · line 253

    Why more general: Mathlib names this language of a machine whose carriers may be infinite and whose start states form a set, where the passage has a finite machine with one start state.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 12cf053d91c0 · pair key 15c46a08bf47.
  17. Definition · main statement · Formal definition › Recognized language

    Formalized

    Formalized by 3 parts together (more general):

    1. NFA.mem_accepts Mathlib (proved)
      • w is accepted exactly when the set of states reached from the start state on w has a member in F
    2. NFA.evalFrom_nil Mathlib (proved)
      • on the empty string the extended transition function returns just the state itself
    3. NFA.evalFrom_append Mathlib (proved)
      • on a string followed by a symbol it returns the union of the transition sets of that symbol over all states reached on the string
    Alternatively, w is accepted if δ∗(q0, w) ∩ F ≠ ∅, where δ∗ : Q × Σ∗ → 𝒫(Q) is defined recursively by: δ∗(r, ε) = {r} where ε is the empty string, and δ∗(r, xa) = ⋃r′ ∈ δ∗(r, x) δ(r′, a) for all x ∈ Σ∗, a ∈ Σ.

    Show in article · Read it in context on Wikipedia

    NFA.mem_accepts states part

    theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x

    Mathlib.Computability.NFA · lines 255–256

    Why only part: Mathlib carries a set of start states and imposes no finiteness on states or symbols, so the singleton {q0} and the article's finite data are an instance of it.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 02b1a53a520f · pair key ca9b72f221a0.

    NFA.evalFrom_nil states part

    theorem NFA.evalFrom_nil {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) : M.evalFrom S [] = S

    Mathlib.Computability.NFA · lines 102–103

    Why only part: The equation is stated for an arbitrary set of states, and the one-element set {r} is the case the article writes.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 254a8a3b5368 · pair key 3310943c7106.

    NFA.evalFrom_append states part

    theorem NFA.evalFrom_append {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) (x y : List α) : M.evalFrom S (x ++ y) = M.evalFrom (M.evalFrom S x) y

    Mathlib.Computability.NFA · lines 118–120

    Why only part: Evaluation on a one-symbol word is by definition Mathlib's step-set operation, namely the union of the transition sets over the current states.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 3 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 0653cc1deef2 · pair key 484fca6f80bc.
  18. Theorem · supporting · Formal definition › Recognized language

    Formalized

    Formalized: Mathlib states a more general result (proved).

    In words, δ∗(r, x) is the set of all states reachable from state r by consuming the string x.

    Show in article · Read it in context on Wikipedia

    NFA.mem_evalFrom_iff_nonempty_path more general

    theorem NFA.mem_evalFrom_iff_nonempty_path {α : Type u} {σ : Type v} {M : NFA α σ} {s t : σ} {x : List α} : t ∈ M.evalFrom {s} x ↔ Nonempty (M.Path s t x)

    Mathlib.Computability.NFA · lines 280–296

    Why more general: Mathlib writes the set element by element and names reachability by its inductive path type, and it puts no finiteness condition on the states or the alphabet.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 2d3fcdd42fd2 · pair key ac646eb63803.
  19. Theorem · supporting · Formal definition › Recognized language

    Formalized

    Formalized: Mathlib states a more general result (proved).

    The string w is accepted if some accepting state in F can be reached from the start state q0 by consuming w.

    Show in article · Read it in context on Wikipedia

    NFA.accepts_iff_exists_path more general

    theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)

    Mathlib.Computability.NFA · lines 298–301

    Why more general: Mathlib allows a set of start states and no finiteness condition, and the article's single start state is the singleton case.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key f778c46c4bb1 · pair key a7014caf9dc5.

    NFA.mem_accepts more general

    theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x

    Mathlib.Computability.NFA · lines 255–256

    Why more general: This phrases the same criterion through the evaluated set of reached states rather than through a path.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 895811518eee · pair key 8cab3d0bf596.
  20. Construction · supporting · Formal definition › Initial state

    Not formalized
    There is an easy construction that translates an NFA with multiple initial states to an NFA with a single initial state, which provides a convenient notation.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt d19b5569ece1).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  21. Definition · main statement · Formal definition › Isomorphism

    Partial

    Partial: Mathlib states part of this (proved).

    An isomorphism φ from an automaton (Q, Σ, δ, q0, F) to an automaton (Q′, Σ, δ′, q′0, F′) is a bijective mapping φ : Q → Q′ such that
    φ(q0) = q′0, q ∈ F if, and only if, φ(q) ∈ F′, for each q ∈ Q, and r ∈ δ(q, a) if, and only if, φ(r) ∈ δ′(φ(q), a), for each q, r ∈ Q and a ∈ Σ.

    Show in article · Read it in context on Wikipedia

    DFA.reindex_apply_start states part

    theorem DFA.reindex_apply_start {α : Type u} {σ : Type v} {σ' : Type*} (g : σ ≃ σ') (M : DFA α σ) : ((DFA.reindex g) M).start = g M.start

    Mathlib.Computability.DFA · line 229

    Why only part: The lemma is stated for deterministic automata, which the article itself counts among its automata, and for the particular second automaton obtained by relabelling along the bijection.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 832a9dca7d33 · pair key 9043038b186e.

    DFA.reindex_apply_accept states part

    theorem DFA.reindex_apply_accept {α : Type u} {σ : Type v} {σ' : Type*} (g : σ ≃ σ') (M : DFA α σ) : ((DFA.reindex g) M).accept = ⇑g.symm ⁻¹' M.accept

    Mathlib.Computability.DFA · line 229

    Why only part: The accepting set of the relabelled automaton is described as the preimage along the inverse bijection, which is the article's two-way condition on accepting states.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 29ede8f593a1 · pair key 0c016b1c9e34.

    DFA.reindex_apply_step states part

    theorem DFA.reindex_apply_step {α : Type u} {σ : Type v} {σ' : Type*} (g : σ ≃ σ') (M : DFA α σ) (s : σ') (a : α) : ((DFA.reindex g) M).step s a = g (M.step (g.symm s) a)

    Mathlib.Computability.DFA · line 229

    Why only part: For deterministic automata the transition set is a single state, so the equation between the two transition functions is the article's two-way condition on transitions.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 472f0554bc41 · pair key 27dd516f4bb5.
  22. Example · supporting · Example

    Not formalized
    The following automaton M, with a binary alphabet, determines if the input ends with a 1.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 96c0d1109fb6).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  23. Theorem · supporting · Example

    Not formalized
    Since the set δ(p, 1) contains more than one state, M is nondeterministic.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 339a0e30cb47).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  24. Theorem · supporting · Example

    Not formalized
    The language of M can be described by the regular language given by the regular expression (0|1)*1.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 0a67d3369bd9).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  25. Theorem · supporting · Example

    Not formalized
    The string is accepted by M since one state sequence satisfies the above definition; it does not matter that other sequences fail to do so.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 9b01628c6982).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  26. Theorem · supporting · Example

    Not formalized
    Considering the first of the above formal definitions, "1011" is accepted since when reading it M may traverse the state sequence ⟨r0, r1, r2, r3, r4⟩ = ⟨p, p, p, p, q⟩, which satisfies conditions 1 to 3.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt b465e3b35a2a).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  27. Theorem · supporting · Example

    Not formalized
    Considering the first of the above formal definitions, "1011" is accepted since when reading it M may traverse the state sequence ⟨r0, r1, r2, r3, r4⟩ = ⟨p, p, p, p, q⟩, which satisfies conditions 1 to 3.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt a46218a63ee3).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  28. Theorem · supporting · Example

    Formalized

    Formalized: Mathlib states a more general result (proved).

    Concerning the second formal definition, bottom-up computation shows that δ∗(p, ε) = {p} , hence δ∗(p, 1) = δ(p, 1) = {p, q}, hence δ∗(p, 10) = δ(p, 0) ∪ δ(q, 0) = {p} ∪ {}, hence δ∗(p, 101) = δ(p, 1) = {p, q}…

    Show in article · Read it in context on Wikipedia

    NFA.evalFrom_nil more general

    theorem NFA.evalFrom_nil {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) : M.evalFrom S [] = S

    Mathlib.Computability.NFA · lines 102–103

    Why more general: The lemma holds for every automaton and every set of starting states, so the passage's case is one instance; mathlib's evalFrom reads a set of states where the article writes the single state p, and the matching set is {p}.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key a449df83fb00 · pair key 723f1eb83038.

    NFA.eval_nil more general

    theorem NFA.eval_nil {α : Type u} {σ : Type v} (M : NFA α σ) : M.eval [] = M.start

    Mathlib.Computability.NFA · lines 237–238

    Why more general: mathlib's eval runs a word from the machine's own start states; for this machine that set is the singleton of p, and the lemma at the empty word returns it unchanged.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 52be15222e2d · pair key 692cd0db7633.
  29. Theorem · supporting · Example

    Not formalized
    Concerning the second formal definition, bottom-up computation shows that δ∗(p, ε) = {p}, hence δ∗(p, 1) = δ(p, 1) = {p, q} , hence δ∗(p, 10) = δ(p, 0) ∪ δ(q, 0) = {p} ∪ {}, hence δ∗(p, 101) = δ(p, 1) = {p, q}, and hence δ∗(p, 1011) = δ(p, 1) ∪ δ(q, 1) = {p, q} ∪ {}…

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 6769c379a421).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  30. Theorem · supporting · Example

    Not formalized
    Concerning the second formal definition, bottom-up computation shows that δ∗(p, ε) = {p}, hence δ∗(p, 1) = δ(p, 1) = {p, q}, hence δ∗(p, 10) = δ(p, 0) ∪ δ(q, 0) = {p} ∪ {} , hence δ∗(p, 101) = δ(p, 1) = {p, q}, and hence δ∗(p, 1011) = δ(p, 1) ∪ δ(q, 1) = {p, q} ∪ {}; since that set is not disjoint from {q}…

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 7827ee2a7dd7).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  31. Theorem · supporting · Example

    Not formalized
    …δ∗(p, ε) = {p}, hence δ∗(p, 1) = δ(p, 1) = {p, q}, hence δ∗(p, 10) = δ(p, 0) ∪ δ(q, 0) = {p} ∪ {}, hence δ∗(p, 101) = δ(p, 1) = {p, q} , and hence δ∗(p, 1011) = δ(p, 1) ∪ δ(q, 1) = {p, q} ∪ {}; since that set is not disjoint from {q}, the string "1011" is accepted.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 300f90fa9f16).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  32. Theorem · supporting · Example

    Not formalized
    …δ∗(p, 1) = δ(p, 1) = {p, q}, hence δ∗(p, 10) = δ(p, 0) ∪ δ(q, 0) = {p} ∪ {}, hence δ∗(p, 101) = δ(p, 1) = {p, q}, and hence δ∗(p, 1011) = δ(p, 1) ∪ δ(q, 1) = {p, q} ∪ {} ; since that set is not disjoint from {q}, the string "1011" is accepted.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 70417acfe8e7).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  33. Theorem · supporting · Example

    Not formalized
    …δ∗(p, 101) = δ(p, 1) = {p, q}, and hence δ∗(p, 1011) = δ(p, 1) ∪ δ(q, 1) = {p, q} ∪ {}; since that set is not disjoint from {q}, the string "1011" is accepted.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt af1492217306).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  34. Theorem · supporting · Example

    Not formalized
    In contrast, the string "10" is rejected by M (all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state, q, by reading the final 0 symbol.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 4e218359928d).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  35. Theorem · supporting · Example

    Not formalized
    In contrast, the string "10" is rejected by M (all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state, q, by reading the final 0 symbol.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt e6f1746b558a).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  36. Theorem · supporting · Example

    Not formalized
    While q can be reached after consuming the initial "1", this does not mean that the input "10" is accepted; rather, it means that an input string "1" would be accepted.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 9152454b4e97).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  37. Definition · main statement · Equivalence to DFA

    Formalized

    Formalized: Mathlib states this exactly (a definition).

    A deterministic finite automaton (DFA) can be seen as a special kind of NFA, in which for each state and symbol, the transition function has exactly one state.

    Show in article · Read it in context on Wikipedia

    DFA.toNFA exact match

    def DFA.toNFA {α : Type u} {σ : Type v} : DFA α σ → NFA α σ

    Mathlib.Computability.NFA · lines 331–334

    Note: The construction keeps the start state and the accept set and sends each state and symbol to the one element set holding the deterministic successor.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 9d286ba7bc88 · pair key bf0477282011.

    DFA.toNFA_step close match

    theorem DFA.toNFA_step {α : Type u} {σ : Type v} (M : DFA α σ) (s : σ) (a : α) : M.toNFA.step s a = {M.step s a}

    Mathlib.Computability.NFA · line 331

    Why close, not exact: The theorem unfolds the transition of the associated NFA to the one element set holding the deterministic successor.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 506cb12a89d0 · pair key 16c92ade9f10.
  38. Theorem · main statement · Equivalence to DFA

    Formalized

    Formalized: Mathlib states a more general result (proved).

    Thus, it is clear that every formal language that can be recognized by a DFA can be recognized by an NFA.

    Show in article · Read it in context on Wikipedia

    DFA.toNFA_correct more general

    theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 348–354

    Why more general: The theorem names an explicit witness automaton for each deterministic one and equates the two recognised languages.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 830ec2027cc5 · pair key e4b5709c7f99.
  39. Theorem · main statement · Equivalence to DFA

    Formalized

    Formalized: Mathlib states a more general result (proved).

    Conversely, for each NFA, there is a DFA such that it recognizes the same formal language.

    Show in article · Read it in context on Wikipedia

    NFA.toDFA_correct more general

    theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 312–315

    Why more general: The theorem equates the language of the subset construction automaton with the language of the given nondeterministic one.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 002ca5ffb9bc · pair key 55db7e507834.
  40. Theorem · supporting · Equivalence to DFA

    Not formalized
    However, if the NFA has n states, the resulting DFA may have up to 2n states, which sometimes makes the construction impractical for large NFAs.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 4f544fd6aad2).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  41. Definition · main statement · NFA with ε-moves

    Partial

    Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.

    Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA.

    Show in article · Read it in context on Wikipedia

    NFA.toεNFA_correct more general

    theorem NFA.toεNFA_correct {α : Type u} {σ : Type v} (M : NFA α σ) : M.toεNFA.accepts = M.accepts

    Mathlib.Computability.EpsilonNFA · lines 350–352

    Why more general: The theorem is stated about the canonical conversion, over arbitrary state and alphabet types, and says the accepted language is unchanged.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key f5463bbcf31b · pair key e1852589d199.
  42. Definition · main statement · NFA with ε-moves

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    In this kind of automaton, the transition function is additionally defined on the empty string ε.

    Show in article · Read it in context on Wikipedia

    εNFA more general

    structure εNFA : Type u → Type v → Type (max u v)

    Mathlib.Computability.EpsilonNFA · lines 40–48

    Why more general: Mathlib gives the transition field the domain of a state together with an optional symbol, and the absent symbol is the epsilon move.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 9701aa10adf3 · pair key bebea0f59ebc.
  43. Definition · supporting · NFA with ε-moves

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    A transition without consuming an input symbol is called an ε-transition and is represented in state diagrams by an arrow labeled "ε".

    Show in article · Read it in context on Wikipedia

    εNFA more general

    structure εNFA : Type u → Type v → Type (max u v)

    Mathlib.Computability.EpsilonNFA · lines 40–48

    Why more general: The documentation of the structure itself calls a move taken on the absent symbol an epsilon-transition, so the library names the notion the passage names.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 73bc1620dd81 · pair key e4b516d49b9d.
  44. Definition · main statement · NFA with ε-moves › Formal definition

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    An NFA-ε is represented formally by a 5-tuple, (Q, Σ, δ, q0, F), consisting of
    a finite set of states Q a finite set of input symbols called the alphabet Σ a transition function δ : Q × (Σ ∪ {ε}) → 𝒫(Q) an initial (or start) state q0 ∈ Q a set of states F distinguished as accepting (or final) states F ⊆ Q.

    Show in article · Read it in context on Wikipedia

    εNFA more general

    structure εNFA : Type u → Type v → Type (max u v)

    Mathlib.Computability.EpsilonNFA · lines 40–48

    Why more general: Mathlib bundles the same five components as type parameters and fields, except that the start data is a set of states and neither the states nor the alphabet are required to be finite.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 50b67808c5ff · pair key 381c95a7566e.
  45. Notation · supporting · NFA with ε-moves › Formal definition

    Partial

    Partial: Mathlib states part of this (a definition).

    Here, 𝒫(Q) denotes the power set of Q and ε denotes empty string.

    Show in article · Read it in context on Wikipedia

    Set.powerset states part

    def Set.powerset {α : Type u} : Set α → Set (Set α)

    Mathlib.Data.Set.Defs · line 255

    Why only part: Mathlib writes this operator with a script-P and defines it for an arbitrary set inside an arbitrary type.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 19de5e21d52e · pair key 36e6c127acb4.
  46. Definition · main statement · NFA with ε-moves › ε-closure of a state or set of states

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    … E(q) denote the set of states that are reachable from q by following ε-transitions in the transition function δ, i.e., p ∈ E(q) if there is a sequence of states q1, ..., qk such that
    q1 = q, qi + 1 ∈ δ(qi, ε) for each 1 ≤ i < k, and qk = p.

    Show in article · Read it in context on Wikipedia

    εNFA.εClosure more general

    def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ

    Mathlib.Computability.EpsilonNFA · line 63

    Why more general: Mathlib defines the closure of a whole set of states; the article's operator on a single state is this one at the one-element set.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 2dcbdd494f6c · pair key e5af81d87554.

    εNFA.mem_εClosure_iff_exists_path more general

    theorem εNFA.mem_εClosure_iff_exists_path {α : Type u} {σ : Type v} (M : εNFA α σ) {s₁ s₂ : σ} : s₂ ∈ M.εClosure {s₁} ↔ ∃ n, M.IsPath s₁ s₂ (List.replicate n Option.none)

    Mathlib.Computability.EpsilonNFA · lines 225–246

    Why more general: The run is recorded as a list of repeated absent symbols, and the traversal predicate fixes its first and last state.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 499843b36442 · pair key 7f2a3d016604.
  47. Definition · main statement · NFA with ε-moves › ε-closure of a state or set of states

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    E(q) is known as the epsilon closure, (also ε-closure) of q.

    Show in article · Read it in context on Wikipedia

    εNFA.εClosure more general

    def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ

    Mathlib.Computability.EpsilonNFA · line 63

    Why more general: Mathlib carries this operator under the epsilon-closure name and documents it as reachability by a finite run of epsilon-moves.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 63984d459867 · pair key 463e1e645003.
  48. Definition · supporting · NFA with ε-moves › ε-closure of a state or set of states

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    The ε-closure of a set P of states of an NFA is defined as the set of states reachable from any state in P following ε-transitions.

    Show in article · Read it in context on Wikipedia

    εNFA.εClosure more general

    def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ

    Mathlib.Computability.EpsilonNFA · line 63

    Why more general: Mathlib's operator takes an arbitrary set of states and returns those reachable from one of its members by a finite run of epsilon-moves.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key c4e634784d03 · pair key 9aa305b6a474.

    εNFA.mem_εClosure_iff_exists more general

    theorem εNFA.mem_εClosure_iff_exists {α : Type u} {σ : Type v} (M : εNFA α σ) {S : Set σ} {s : σ} : s ∈ M.εClosure S ↔ ∃ t ∈ S, s ∈ M.εClosure {t}

    Mathlib.Computability.EpsilonNFA · lines 104–115

    Why more general: The library writes the union over the members of the set elementwise rather than as an equality of two sets.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 824c631443c2 · pair key 10994db2daa6.
  49. Definition · supporting · NFA with ε-moves › ε-closure of a state or set of states

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    Formally, for P ⊆ Q, define E(P) = ⋃q ∈ P E(q).

    Show in article · Read it in context on Wikipedia

    εNFA.εClosure more general

    def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ

    Mathlib.Computability.EpsilonNFA · line 63

    Why more general: Mathlib lets the state type be infinite, of which the article's finite Q is one case, and marks an ε-transition by the label none instead of the letter ε.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 4058eda6d50d · pair key 0d309b3b7fed.

    εNFA.mem_εClosure_iff_exists more general

    theorem εNFA.mem_εClosure_iff_exists {α : Type u} {σ : Type v} (M : εNFA α σ) {S : Set σ} {s : σ} : s ∈ M.εClosure S ↔ ∃ t ∈ S, s ∈ M.εClosure {t}

    Mathlib.Computability.EpsilonNFA · lines 104–115

    Why more general: The equality of the two sets is phrased as a membership equivalence, and the closure of a one-element set plays the role of the article's closure of a single state.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 6c9a4534a1b4 · pair key 5ce5a276b0d5.
  50. Notation · supporting · NFA with ε-moves › Extended transition function

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    Informally, δ∗(q, w) denotes the set of all states the automaton may have reached when starting in state q ∈ Q and reading the string w ∈ Σ∗. The function δ∗ : Q × Σ∗ → 𝒫(Q) can be defined recursively as follows.

    Show in article · Read it in context on Wikipedia

    εNFA.evalFrom more general

    def εNFA.evalFrom {α : Type u} {σ : Type v} : εNFA α σ → Set σ → List α → Set σ

    Mathlib.Computability.EpsilonNFA · lines 135–136

    Why more general: Mathlib starts the computation from a set of states rather than one state and allows infinitely many states, and strings are lists of alphabet letters.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 2e1e40065da4 · pair key e76ed23fabd0.
  51. Definition · main statement · NFA with ε-moves › Extended transition function

    Partial

    Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.

    δ∗(q, ε) = E(q), for each state q ∈ Q, and where E denotes the epsilon closure;

    Show in article · Read it in context on Wikipedia

    εNFA.evalFrom_nil more general

    theorem εNFA.evalFrom_nil {α : Type u} {σ : Type v} (M : εNFA α σ) (S : Set σ) : M.evalFrom S [] = M.εClosure S

    Mathlib.Computability.EpsilonNFA · lines 139–140

    Why more general: Mathlib states the base case for a whole set of starting states, and the empty string is the empty list of letters.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 5ccf03f1a18c · pair key 458660dac0c6.
  52. Definition · main statement · NFA with ε-moves › Extended transition function

    Partial

    Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.

    Informally: Reading the empty string may drive the automaton from state q to any state of the epsilon closure of q.
    δ∗(q, wa) = ⋃r ∈ δ∗(q, w) E(δ(r, a)), for each state q ∈ Q, each string w ∈ Σ∗ and each symbol a ∈ Σ.

    Show in article · Read it in context on Wikipedia

    εNFA.evalFrom_append_singleton more general

    theorem εNFA.evalFrom_append_singleton {α : Type u} {σ : Type v} (M : εNFA α σ) (S : Set σ) (x : List α) (a : α) : M.evalFrom S (x ++ [a]) = M.stepSet (M.evalFrom S x) a

    Mathlib.Computability.EpsilonNFA · lines 147–149

    Why more general: Mathlib writes the union through its one-letter step operation on sets and encodes reading the letter a as the labelled option some a.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 499176ee803e · pair key 0a1e8c476e7d.
  53. Definition · main statement · NFA with ε-moves › Extended transition function

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    The automaton is said to accept a string w if δ∗(q0, w) ∩ F ≠ ∅, that is, if reading w may drive the automaton from its start state q0 to some accepting state in F.

    Show in article · Read it in context on Wikipedia

    εNFA.accepts more general

    def εNFA.accepts {α : Type u} {σ : Type v} : εNFA α σ → Language α

    Mathlib.Computability.EpsilonNFA · lines 183–184

    Why more general: Mathlib collects the accepted inputs into a language of lists and lets the automaton carry a set of initial states; asking for an accepting state in the reached set is the same as asking that the reached set meet the accepting ones.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key aea3ef9cb6f4 · pair key 58d27555fa28.
  54. Example · supporting · NFA with ε-moves › Example

    Not formalized
    Let M be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt d1a3502277e1).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  55. Theorem · supporting · NFA with ε-moves › Example

    Formalized

    Formalized: Mathlib states a more general result (proved).

    Note that 0 occurrences is an even number of occurrences as well.

    Show in article · Read it in context on Wikipedia

    Even.zero more general

    theorem Even.zero {α : Type*} [AddZeroClass α] : Even 0

    Mathlib.Algebra.Group.Even · line 104

    Why more general: Mathlib states this for any type with addition and a zero, of which the counts of occurrences are one case, and being even there means being the sum of something with itself.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key c33fc5f8cb11 · pair key e6b2cc752f9f.
  56. Theorem · supporting · NFA with ε-moves › Example

    Not formalized
    M can be viewed as the union of two DFAs: one with states {S1, S2} and the other with states {S3, S4}.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt 97a8cd77ce9c).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  57. Theorem · supporting · NFA with ε-moves › Example

    Not formalized
    The language of M can be described by the regular language given by this regular expression (1∗01∗01∗)∗ ∪ (0∗10∗10∗)∗.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 5 queries and 3 candidates examined (receipt 219a34231fb4).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  58. Theorem · supporting · NFA with ε-moves › Example

    Formalized

    Formalized: Mathlib states a more general result (proved).

    We define M using ε-moves but M can be defined without using ε-moves.

    Show in article · Read it in context on Wikipedia

    εNFA.toNFA_correct more general

    theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts

    Mathlib.Computability.EpsilonNFA · lines 312–313

    Why more general: The ε-free automaton the lemma produces is Lean's own conversion, so the machine it exhibits need not be the one a reader would draw by hand.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key e01d6a0050fe · pair key a928ecdb6c6f.
  59. Theorem · supporting · NFA with ε-moves › Equivalence to NFA

    Formalized

    Formalized: Mathlib states this up to a convention difference (proved).

    To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε, so it remains to show for every NFA-ε, there exists an equivalent NFA.

    Show in article · Read it in context on Wikipedia

    NFA.toεNFA_correct close match

    theorem NFA.toεNFA_correct {α : Type u} {σ : Type v} (M : NFA α σ) : M.toεNFA.accepts = M.accepts

    Mathlib.Computability.EpsilonNFA · lines 350–352

    Why close, not exact: Lean keeps the two kinds of automaton as distinct types, so the inclusion is encoded as a conversion that reuses the states, the start and accept sets and the transitions and adds no ε-step, and the lemma records that the accepted language is unchanged.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key aa28077a159a · pair key f5c3d48a7512.
  60. Construction · main statement · NFA with ε-moves › Equivalence to NFA

    Not formalized
    Given an NFA with epsilon moves M = (Q, Σ, δ, q0, F), define an NFA M′ = (Q, Σ, δ′, q0, F′), where F′ = {F ∪ {q0} if E(q0) ∩ F ≠ {}F otherwise and δ′(q, a) = δ∗(q, a) for each state q ∈ Q and each symbol a ∈ Σ, using the extended transition function δ∗ defined above.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt 49224640f750).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  61. Theorem · supporting · NFA with ε-moves › Equivalence to NFA

    Not formalized
    By construction, M′ has no ε-transitions.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt e913751997e7).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  62. Theorem · supporting · NFA with ε-moves › Equivalence to NFA

    Not formalized
    One can prove that δ′∗(q0, w) = δ∗(q0, w) for each string w ≠ ε, by induction on the length of w.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt f23c0b017883).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  63. Theorem · main statement · NFA with ε-moves › Equivalence to NFA

    Not formalized
    Based on this, one can show that δ′∗(q0, w) ∩ F′ ≠ {} if, and only if, δ∗(q0, w) ∩ F ≠ {}, for each string w ∈ Σ∗ :

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt 23be13ea74a5).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  64. Theorem · supporting · NFA with ε-moves › Equivalence to NFA

    Not formalized
    Otherwise, let w = va with v ∈ Σ∗ and a ∈ Σ.
    From δ′∗(q0, w) = δ∗(q0, w) and F ⊆ F′, we have δ′∗(q0, w) ∩ F′ ≠ {}  ⇐ δ∗(q0, w) ∩ F ≠ {}; we still have to show the " ⇒ " direction.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt c2ce124a9751).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  65. Theorem · supporting · NFA with ε-moves › Equivalence to NFA

    Not formalized
    If δ′∗(q0, w) contains a state in F′ ∖ {q0}, then δ∗(q0, w) contains the same state, which lies in F.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 4985b5fead19).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  66. Theorem · supporting · NFA with ε-moves › Equivalence to NFA

    Not formalized
    If δ′∗(q0, w) contains q0, and q0 ∈ F, then δ∗(q0, w) also contains a state in F, viz. q0. If δ′∗(q0, w) contains q0, and q0 ∉ F, but q0 ∈ F′, then there exists a state in E(q0) ∩ F, and the same state must be in δ∗(q0, w) = ⋃r ∈ δ∗(q, v) E(δ(r, a)).…

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt f15251ce4cdb).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  67. Theorem · supporting · NFA with ε-moves › Equivalence to NFA

    Not formalized
    q0. If δ′∗(q0, w) contains q0, and q0 ∉ F, but q0 ∈ F′, then there exists a state in E(q0) ∩ F, and the same state must be in δ∗(q0, w) = ⋃r ∈ δ∗(q, v) E(δ(r, a)).

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt 1d198b10aee9).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  68. Theorem · main statement · NFA with ε-moves › Equivalence to NFA

    Not formalized
    Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 0 candidates examined (receipt 57eb0efc7df6).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  69. Theorem · main statement · Closure properties

    Partial

    Partial: Mathlib states part of this (proved).

    They can also be used to prove that NFAs recognize exactly the regular languages.

    Show in article · Read it in context on Wikipedia

    NFA.toDFA_correct states part

    theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 312–315

    Why only part: Mathlib puts no finiteness demand on the state type, so the finiteness the regular-language predicate wants comes from the passage's own automaton.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 47726ec03bd5 · pair key 4f66decac9aa.

    DFA.toNFA_correct states part

    theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 348–354

    Why only part: The converted automaton keeps the state set, so the finiteness the passage expects of an automaton is preserved.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 1d8839b32b85 · pair key ce67faa15340.
  70. Theorem · main statement · Closure properties

    Partial

    Partial: Mathlib states a special case (proved).

    Union (cf. picture); that is, if the language L1 is accepted by some NFA A1 and L2 by some A2, then an NFA Au can be constructed that accepts the language L1∪L2.

    Show in article · Read it in context on Wikipedia

    Language.IsRegular.add special case

    theorem Language.IsRegular.add {T : Type u} {L1 L2 : Language T} : L1.IsRegular → L2.IsRegular → (L1 + L2).IsRegular

    Mathlib.Computability.DFA · lines 390–394

    Why a special case: Mathlib phrases the closure with its recognizability predicate, whose witness is a finite deterministic machine, and the index links that model to the nondeterministic one by its two conversion theorems; the sum of two languages is their union.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack, which downgraded it.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 203ab2bbfd70 · pair key 5387021dab4a.
  71. Theorem · main statement · Closure properties

    Partial

    Partial: Mathlib states a special case (proved).

    Intersection; similarly, from A1 and A2 an NFA Ai can be constructed that accepts L1∩L2.

    Show in article · Read it in context on Wikipedia

    Language.IsRegular.inf special case

    theorem Language.IsRegular.inf {T : Type u} {L1 L2 : Language T} : L1.IsRegular → L2.IsRegular → (L1 ⊓ L2).IsRegular

    Mathlib.Computability.DFA · lines 397–401

    Why a special case: Mathlib phrases the closure with its recognizability predicate, whose witness is a finite deterministic machine, and the index links that model to the nondeterministic one by its two conversion theorems; the meet of two languages is their intersection.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack, which downgraded it.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key bc4df89185c4 · pair key cb48ccc03bdf.
  72. Theorem · main statement · Closure properties

    Not formalized
    Concatenation

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt bdb15dc55183).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  73. Theorem · main statement · Closure properties

    Partial

    Partial: Mathlib states a special case (proved).

    Concatenation
    Negation; similarly, from A1 an NFA An can be constructed that accepts Σ*\L1.

    Show in article · Read it in context on Wikipedia

    DFA.accepts_compl special case

    theorem DFA.accepts_compl {α : Type u} {σ : Type v} (M : DFA α σ) : Mᶜ.accepts = M.acceptsᶜ

    Mathlib.Computability.DFA · lines 287–288

    Why a special case: Mathlib carries out the complementation only for deterministic machines, which are the deterministic cases of the article's A1, and its complement is taken inside the set of all strings over the alphabet.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key c6d2b0a862c0 · pair key ca60234ae1ce.
  74. Theorem · main statement · Closure properties

    Not formalized
    Kleene closure

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt 21c405dcec3a).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  75. Definition · supporting · Properties

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.

    Show in article · Read it in context on Wikipedia

    NFA.mem_accepts more general

    theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x

    Mathlib.Computability.NFA · lines 255–256

    Why more general: Lean reads being in an accepting state at the end as the evaluated set of reachable states meeting the set of accepting states, and allows an arbitrary state type where the article keeps a finite one.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 7948e8dbc313 · pair key d208bf248be5.

    NFA.accepts more general

    def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α

    Mathlib.Computability.NFA · line 253

    Why more general: This is the defined object behind the acceptance rule, given for an arbitrary state type and so for more machines than the article's finite ones.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 03c81913f743 · pair key f6c57827791b.
  76. Definition · supporting · Properties

    Formalized

    Formalized: Mathlib states a more general result (a definition).

    The set of all strings accepted by an NFA is the language the NFA accepts.

    Show in article · Read it in context on Wikipedia

    NFA.accepts more general

    def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α

    Mathlib.Computability.NFA · line 253

    Why more general: Lean packages the collection as a language over the alphabet and allows any state type, which covers more machines than the article's finite ones.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key c98804e6d3cc · pair key a3e64e927a4f.
  77. Theorem · supporting · Properties

    Formalized

    Formalized: Mathlib states a more general result (proved).

    This language is a regular language.

    Show in article · Read it in context on Wikipedia

    NFA.toDFA_correct more general

    theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 312–315

    Why more general: Mathlib states the subset construction for an arbitrary state type and leaves the step to the word regular to the definition of a regular language, which asks exactly for a deterministic machine with finitely many states.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 4ed4627220bc · pair key dc9a765c7e94.
  78. Theorem · supporting · Properties

    Formalized

    Formalized: Mathlib states a more general result (proved).

    For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.

    Show in article · Read it in context on Wikipedia

    NFA.toDFA_correct more general

    theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 312–315

    Why more general: Mathlib names the deterministic machine instead of merely asserting that one can be found, and states it for an arbitrary state type, so it covers more machines than the article's finite ones.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 85b8db265606 · pair key 69df436e9f53.
  79. Theorem · supporting · Implementation

    Not formalized
    Each step requires at most s2 computations, where s is the number of states of the NFA.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 71f85982832d).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  80. Theorem · supporting · Implementation

    Not formalized
    A string of length n can be processed in time O(ns2),[15] and space O(s).

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt 0be8a2631afd).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  81. Theorem · supporting · Implementation

    Not formalized
    (This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt c538c3b2ac38).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  82. Theorem · main statement · Complexity

    Not formalized
    One can solve in linear time the emptiness problem for NFA, i.e., check whether the language of a given NFA is empty.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 8725087e8ec8).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  83. Theorem · main statement · Complexity

    Not formalized
    It is PSPACE-complete to test, given an NFA, whether it is universal, i.e., if there is a string that it does not accept.[17]

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 00e356120198).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  84. Theorem · supporting · Complexity

    Not formalized
    As a consequence, the same is true of the inclusion problem, i.e., given two NFAs, is the language of one a subset of the language of the other.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt cd052a28a68d).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  85. Theorem · supporting · Complexity

    Not formalized
    Given as input an NFA A and an integer n, the counting problem of determining how many words of length n are accepted by A is intractable; it is #P-hard.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt ac64e7dfe44b).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  86. Theorem · supporting · Complexity

    Not formalized
    Given as input an NFA A and an integer n, the counting problem of determining how many words of length n are accepted by A is intractable; it is #P-hard.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 6e5742eb9cb6).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  87. Theorem · supporting · Complexity

    Not formalized
    In fact, this problem is complete (under parsimonious reductions) for the complexity class SpanL.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 3674e658f362).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  88. Theorem · supporting · Application of NFA

    Partial

    Partial: Mathlib states part of this (proved).

    NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa.

    Show in article · Read it in context on Wikipedia

    NFA.toDFA_correct states part

    theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts

    Mathlib.Computability.NFA · lines 312–315

    Why only part: This gives the direction from a nondeterministic machine to a deterministic one; the reverse direction of the stated equivalence is not asserted here.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 6f4d2d18b3a5 · pair key d1cad8ed1028.

Data: view model (JSON) · Literature Links records (JSONL)