AFTD Auto-Formalizing Theoretical Domains

dfa_is_synchronizable

def

A deterministic finite automaton A : DFA α σ is synchronizable if there exists a synchronizing word w : List α for A.

Statement

def dfa_is_synchronizable {α σ : Type*} (A : DFA α σ) : Prop
Defined in
arXiv:2611.09136 Sec. 2
Verified
09 Nov 2026
Axioms
none listed
Built on 1
  • dfa_is_synchronizingA word w : List α is synchronizing for a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all…
Used by 7

Read back from the Lean

For types α and σ, and a deterministic finite automaton A : DFA α σ, dfa_is_synchronizable A asserts that there exists a word w : List α such that for all states q₁, q₂ : σ, evaluating A starting from q₁ on w results in the same state as evaluating A starting from q₂ on w (that is, A.evalFrom q₁ w = A.evalFrom q₂ w).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A DFA is synchronizable if it admits a synchronizing word. -/
def dfa_is_synchronizable {α σ : Type*} (A : DFA α σ) : Prop := ∃ w : List α, dfa_is_synchronizing A w
See it in the graphDiscuss this resultChallenge it