dfa_is_synchronizable_subsingleton
Every deterministic finite automaton whose state type is a subsingleton is synchronizable.
Statement
theorem dfa_is_synchronizable_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) : dfa_is_synchronizable A
- Source
- folklore
- Verified
- 09 Nov 2026
- Axioms
Quot.soundpropext- Built on 3
- dfa_is_synchronizableA deterministic finite automaton
A : DFA α σis synchronizable if there exists a synchronizing wordw : List αforA. - dfa_is_synchronizing_subsingletonEvery word is synchronizing for a deterministic finite automaton whose state type is a subsingleton.
- dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all…
- dfa_is_synchronizableA deterministic finite automaton
Read back from the Lean
For all types α and σ where σ is a subsingleton (has at most one element), and for every deterministic finite automaton A : DFA α σ, A is synchronizable.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
A deterministic finite automaton is synchronizable if there exists an input word that takes all states to the same state. When the state space is a subsingleton, any two states are already equal, so every word is synchronizing. The theorem is proved by exhibiting the empty word as an explicit witness and invoking `dfa_is_synchronizing_subsingleton`.
The automaton $A$ is synchronizable.
By definition, an automaton is synchronizable if there exists some word that transitions every state to the same state. The proof provides the empty word `[]` as an explicit witness, and satisfies the requirement that it is synchronizing using `dfa_is_synchronizing_subsingleton`, which holds because the state type $\sigma$ is a subsingleton.
uses
dfa_is_synchronizing_subsingletontheorem dfa_is_synchronizable_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) : dfa_is_synchronizable A := ⟨[], dfa_is_synchronizing_subsingleton A []⟩
dfa_is_synchronizing_subsingleton- For any deterministic finite automaton whose state type is a subsingleton, every input word is synchronizing.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Sanity lemma: a DFA on a subsingleton state type is synchronizable. -/theorem dfa_is_synchronizable_subsingleton {α σ : Type*} [Subsingleton σ] (A : DFA α σ) : dfa_is_synchronizable A := ⟨[], dfa_is_synchronizing_subsingleton A []⟩