-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Related, but states something else
DFA.toNFA related
def DFA.toNFA {α : Type u} {σ : Type v} : DFA α σ → NFA α σ
Mathlib.Computability.NFA · lines 331–334
How it differs: The construction that reads a deterministic machine as a nondeterministic one, with singleton step sets; by itself it carries no claim about the words accepted.
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
005819f35953 · pair key 060e1d82514a.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.toDFA related
def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)
Mathlib.Computability.NFA · lines 306–309
How it differs: The construction itself, whose states are sets of the original states and whose step is the one-symbol image of a set of states; on its own it says nothing about accepted words.
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
2c0f9d0e1827 · pair key 9077c33c483d.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.toDFA_correct related
theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts
Mathlib.Computability.NFA · lines 312–315
How it differs: It equates the language of a nondeterministic machine with that of its determinisation; reaching regularity needs in addition that sets over a finite state set form a finite type and Mathlib's characterisation of regular 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 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
c518b1eb0919 · pair key 63e30b6a7a7e.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
Definition · main statement · Formal definition › Recognized language
✓Formalized
Formalized by 3 parts together (more general):
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
NFA.evalFrom_nil Mathlib (proved)- on the empty string the extended transition function returns just the state itself
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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).
Related, but states something else
NFA.mem_accepts related
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
How it differs: It is the acceptance test for an arbitrary automaton and an arbitrary word; it fixes no transition table, so the verdict on this two-state machine and this word is beyond what it says.
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
6a87465c8308 · pair key 28fbe8d5643a.
Sign in to tag this passage
-
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).
Related, but states something else
NFA.accepts_iff_exists_path related
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
How it differs: This is the run-based reading of acceptance for an arbitrary automaton: a word is in the language exactly when some run joins a start state to an accepting one. It settles no concrete 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, 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
db5ecabebade · pair key d45369de5cf9.
Sign in to tag this passage
-
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).
Related, but states something else
NFA.Path related
inductive NFA.Path {α : Type u} {σ : Type v} : NFA α σ → σ → σ → List α → Type (max u v)
Mathlib.Computability.NFA · lines 269–272
How it differs: The inductive family of concrete runs of an arbitrary automaton between two states for a given word; it is the vocabulary in which the passage's run would be written, not an assertion that this run exists.
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
0058416629e8 · pair key e8d4b4a97ef0.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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).
Related, but states something else
NFA.evalFrom_singleton related
theorem NFA.evalFrom_singleton {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) (a : α) : M.evalFrom S [a] = M.stepSet S a
Mathlib.Computability.NFA · lines 107–108
How it differs: For any automaton and any starting set it rewrites a one-letter word as a single transition step; that is the intermediate move of the displayed chain, while the value the chain ends at is read off this machine's table.
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
41afe584c42b · pair key 7889a2c27aef.
NFA.stepSet_singleton related
theorem NFA.stepSet_singleton {α : Type u} {σ : Type v} (M : NFA α σ) (s : σ) (a : α) : M.stepSet {s} a = M.step s a
Mathlib.Computability.NFA · lines 84–85
How it differs: A step from a one-element set of states is the transition of that state, for any automaton; the pair of states the passage records comes from this machine's table instead.
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
64a96d6797f4 · pair key 76dede3c1a60.
Sign in to tag this passage
-
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).
Related, but states something else
NFA.evalFrom_append related
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
How it differs: It splits a word in two and runs the pieces in turn, for any automaton and starting set; that recursion is how the article moves from one prefix to the next, but the sets it lands in come from this machine's table.
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
21d96035e04a · pair key 52d11db5d7ec.
NFA.stepSet related
def NFA.stepSet {α : Type u} {σ : Type v} : NFA α σ → Set σ → α → Set σ
Mathlib.Computability.NFA · lines 72–73
How it differs: The definition of one step from a set of states as the union of the transitions of its members, for any automaton; the union the passage displays is an instance of that shape with values this machine's table supplies.
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
62e1badccef1 · pair key 674277b30a4f.
Sign in to tag this passage
-
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).
Related, but states something else
NFA.evalFrom_append related
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
How it differs: For any automaton it runs a word prefix first and the rest afterwards, which is the recursion carrying the article from the prefix 10 to the prefix 101; the resulting states are those this machine's table gives.
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
346c77c92089 · pair key 9a4b6725e603.
NFA.stepSet_singleton related
theorem NFA.stepSet_singleton {α : Type u} {σ : Type v} (M : NFA α σ) (s : σ) (a : α) : M.stepSet {s} a = M.step s a
Mathlib.Computability.NFA · lines 84–85
How it differs: A step from a one-element set of states is that state's transition, for any automaton; which pair of states the letter 1 then yields is settled by the table the article displays.
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. - 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
86e314496916 · pair key 593fce4aba73.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.evalFrom_append related
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
How it differs: For any automaton it runs a prefix and then the remaining letter, which is the recursion that takes the article from 101 to the full word; the sets it names come from this machine's table.
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
663b0adebd06 · pair key 6bb40415d0a5.
NFA.stepSet_union related
theorem NFA.stepSet_union {α : Type u} {σ : Type v} (M : NFA α σ) {S T : Set σ} {a : α} : M.stepSet (S ∪ T) a = M.stepSet S a ∪ M.stepSet T a
Mathlib.Computability.NFA · lines 89–92
How it differs: A step from a union of two sets of states is the union of the two steps, for any automaton; the union the passage displays has that shape, with values read off this machine's table.
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
4e1e8c1c5dca · pair key ede14e8da5c6.
Sign in to tag this passage
-
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).
Related, but states something else
NFA.mem_accepts related
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
How it differs: It is the general acceptance test, not a claim about the article's 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, 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
5be39f003bfd · pair key 881195f739a5.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.mem_accepts related
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
How it differs: Its negation would express rejection, but only for an arbitrary 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. - 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
528c0c3bce33 · pair key 702363daf93e.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.mem_stepSet related
theorem NFA.mem_stepSet {α : Type u} {σ : Type v} {M : NFA α σ} {s : σ} {S : Set σ} {a : α} : s ∈ M.stepSet S a ↔ ∃ t ∈ S, s ∈ M.step t a
Mathlib.Computability.NFA · lines 75–76
How it differs: It unfolds which states one step on a symbol can reach, for any 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. - 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
333c31f1e7ff · pair key 00a1053f2831.
Sign in to tag this passage
-
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).
Related, but states something else
NFA.mem_accepts related
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
How it differs: It is the general acceptance test applied to any word, including one-letter words.
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
6a8e989b4ed3 · pair key 86193fa72e37.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Related, but states something else
DFA.toNFA related
def DFA.toNFA {α : Type u} {σ : Type v} : DFA α σ → NFA α σ
Mathlib.Computability.NFA · lines 331–334
How it differs: It supplies the witness automaton but makes no claim about 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 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
92e637997278 · pair key c03747664c85.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.toDFA related
def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)
Mathlib.Computability.NFA · lines 306–309
How it differs: It is the subset construction itself, with no claim about 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 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
723e5e9229b5 · pair key f28f2e3bba9a.
Sign in to tag this passage
-
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.
Related, but states something else
Fintype.card_set related
theorem Fintype.card_set {α : Type*} [Fintype α] : Fintype.card (Set α) = 2 ^ Fintype.card α
Mathlib.Data.Fintype.Powerset · lines 68–69
How it differs: The theorem counts the sets of states of a finite state type, and that count is the number of states of the automaton the subset construction produces.
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
f0a751123f7d · pair key d9e8dbf56483.
NFA.toDFA related
def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)
Mathlib.Computability.NFA · lines 306–309
How it differs: Its type shows the built automaton has sets of states as states, with no count attached.
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. - 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
7c011c0babf2 · pair key 7a1701bee36b.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.toεNFA related
def NFA.toεNFA {α : Type u} {σ : Type v} : NFA α σ → εNFA α σ
Mathlib.Computability.EpsilonNFA · lines 327–330
How it differs: This is only the conversion map; on its own it does not record that the two machines accept the same words.
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, 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
631d587164dd · pair key 2501e1811463.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Related, but states something else
εNFA.stepSet related
def εNFA.stepSet {α : Type u} {σ : Type v} : εNFA α σ → Set σ → α → Set σ
Mathlib.Computability.EpsilonNFA · lines 118–119
How it differs: This is the operation whose definition supplies the union of ε-closures appearing on the right of the passage's equation, but on its own it says nothing about evaluating a string.
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
ba4e3e67744c · pair key 12dedac51ff5.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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.
Related, but states something else
εNFA.toNFA related
def εNFA.toNFA {α : Type u} {σ : Type v} : εNFA α σ → NFA α σ
Mathlib.Computability.EpsilonNFA · lines 301–304
How it differs: This is the conversion that removes the ε-steps; on its own it asserts nothing about the language of the machine it builds.
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
986fc327f904 · pair key 890ea2b30a3b.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.toεNFA related
def NFA.toεNFA {α : Type u} {σ : Type v} : NFA α σ → εNFA α σ
Mathlib.Computability.EpsilonNFA · lines 327–330
How it differs: The conversion by itself, documented as reusing the start and accept states and the transitions, but stating nothing about 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 2 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
d043fcf2f8b0 · pair key 3a044503fc28.
Sign in to tag this passage
-
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.
Related, but states something else
εNFA.toNFA related
def εNFA.toNFA {α : Type u} {σ : Type v} : εNFA α σ → NFA α σ
Mathlib.Computability.EpsilonNFA · lines 301–304
How it differs: Lean's conversion builds an ε-free automaton from one with ε-moves, but not by the passage's two equations: because its automata carry a set of start states it closes that set under ε-steps and leaves the accepting states alone, instead of adding the start state to them.
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
2e90011fdbd2 · pair key 06ecfae4dcf0.
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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).
Related, but states something else
εNFA.toNFA_evalFrom_match related
theorem εNFA.toNFA_evalFrom_match {α : Type u} {σ : Type v} (M : εNFA α σ) (start : Set σ) : M.toNFA.evalFrom (M.εClosure start) = M.evalFrom start
Mathlib.Computability.EpsilonNFA · lines 307–309
How it differs: It matches the evaluations of Lean's converted machine and the original one, but only after the ε-closure is applied to the start set, and for a conversion whose transitions differ from the passage's.
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
a88bc7967997 · pair key 951f25c39ded.
Sign in to tag this passage
-
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.
Related, but states something else
εNFA.toNFA_correct related
theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts
Mathlib.Computability.EpsilonNFA · lines 312–313
How it differs: The universe does prove that removing ε-steps preserves the accepted language, but for its own conversion, whose start set is ε-closed and whose accepting states are untouched, so it is a statement about another machine than the one the passage built.
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
1853550c8ff6 · pair key 7251b257c2e8.
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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).
Related, but states something else
εNFA.toNFA_evalFrom_match related
theorem εNFA.toNFA_evalFrom_match {α : Type u} {σ : Type v} (M : εNFA α σ) (start : Set σ) : M.toNFA.evalFrom (M.εClosure start) = M.evalFrom start
Mathlib.Computability.EpsilonNFA · lines 307–309
How it differs: Mathlib converts an automaton with epsilon-moves by taking the epsilon closure of the start set and keeping the accepting set, so it never speaks of the article's enlarged accepting 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
9c8f122281c7 · pair key 20831d89800f.
εNFA.toNFA_correct related
theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts
Mathlib.Computability.EpsilonNFA · lines 312–313
How it differs: This is the whole correctness statement of a different conversion, not the article's case analysis on where an accepting state of the new automaton came from.
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. - 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
629b4d9e74a9 · pair key 83965facfcf6.
Sign in to tag this passage
-
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).
Related, but states something else
εNFA.subset_εClosure related
theorem εNFA.subset_εClosure {α : Type u} {σ : Type v} (M : εNFA α σ) (S : Set σ) : S ⊆ M.εClosure S
Mathlib.Computability.EpsilonNFA · line 65
How it differs: It only records that a set of states is contained in its own epsilon closure, which is a background fact rather than the passage's conditional claim.
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
dd3219ffe850 · pair key bc1577887946.
Sign in to tag this passage
-
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).
Related, but states something else
εNFA.eval_nil related
theorem εNFA.eval_nil {α : Type u} {σ : Type v} (M : εNFA α σ) : M.eval [] = M.εClosure M.start
Mathlib.Computability.EpsilonNFA · lines 171–172
How it differs: It computes the set reached on the empty word as the epsilon closure of the start set, which is the object the first conjunct mentions but not the claim made about 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. - 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
4769b772b757 · pair key 414ea9c789d7.
Sign in to tag this passage
-
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.
Related, but states something else
εNFA.toNFA_correct related
theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts
Mathlib.Computability.EpsilonNFA · lines 312–313
How it differs: The declaration lands in the epsilon-free model; the index ties that model to the deterministic one by its own pair of conversion theorems, which I read as two presentations of the recognizable languages rather than as a further hypothesis.
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
46faecb2f218 · pair key 03f5e3174b3a.
NFA.toεNFA_correct related
theorem NFA.toεNFA_correct {α : Type u} {σ : Type v} (M : NFA α σ) : M.toεNFA.accepts = M.accepts
Mathlib.Computability.EpsilonNFA · lines 350–352
How it differs: It supplies the easy inclusion of the equivalence, the one the article disposes of by calling the smaller model a special case of the larger.
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, 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
b40461e2ed3e · pair key 37aaa5362a45.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Related, but states something else
RegularExpression.matches'_mul related
theorem RegularExpression.matches'_mul {α : Type*} (P Q : RegularExpression α) : (P * Q).matches' = P.matches' * Q.matches'
Mathlib.Computability.RegularExpressions · lines 119–120
How it differs: It gives concatenation closure for the languages denoted by regular expressions, and this universe holds no theorem connecting that class to the automaton-recognizable 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
33d769b637e4 · pair key 37d859095424.
Sign in to tag this passage
-
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.
Related, but states something else
Language.IsRegular.compl related
theorem Language.IsRegular.compl {T : Type u} {L : Language T} : L.IsRegular → Lᶜ.IsRegular
Mathlib.Computability.DFA · lines 376–378
How it differs: Closure under complement is stated for languages defined by a finite deterministic machine, so carrying it to the article's nondeterministic machines needs the subset construction in both directions.
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
ad7220b39e3f · pair key 15e7a6bf0a2a.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Related, but states something else
Language.isRegular_iff related
theorem Language.isRegular_iff {T : Type u} {L : Language T} : L.IsRegular ↔ ∃ σ x M, M.accepts = L
Mathlib.Computability.DFA · lines 372–374
How it differs: It fixes what being regular means, a finite-stated deterministic machine accepting the language, but says nothing about machines that are nondeterministic.
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. - 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
45040fa5dbb5 · pair key 22b4c55e7f51.
Sign in to tag this passage
-
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.
Related, but states something else
NFA.toDFA related
def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)
Mathlib.Computability.NFA · lines 306–309
How it differs: It is the subset construction itself, data rather than a claim, and on its own says nothing about the language of the machine it builds.
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. - 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
a3ba7a2bab35 · pair key 611df3a336da.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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.
Sign in to tag this passage
-
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).
Sign in to tag this passage
-
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.
Related, but states something else
DFA.toNFA_correct related
theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts
Mathlib.Computability.NFA · lines 348–354
How it differs: This gives only the converse direction, from a deterministic machine to a nondeterministic one, and not the direction handled by the subset construction.
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, 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
db2807c42f65 · pair key 880804f9260c.
Sign in to tag this passage