AFTD Auto-Formalizing Theoretical Domains

dfa_is_synchronizing

def

A word w : List α is synchronizing for a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all states q₁ q₂ : σ.

Statement

def dfa_is_synchronizing {α σ : Type*} (A : DFA α σ) (w : List α) : Prop
Defined in
arXiv:2611.09136 Section 2
Verified
09 Nov 2026
Axioms
none listed
Used by 23

Read back from the Lean

For an alphabet type α, a state type σ, a deterministic finite automaton A : DFA α σ, and a word w : List α, dfa_is_synchronizing A w asserts that for all states q₁, q₂ : σ, evaluating A on word w starting from q₁ results in the same state as evaluating A on word w starting from q₂.

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 word w is synchronizing for a DFA A if it maps all states to the same state. -/
def dfa_is_synchronizing {α σ : Type*} (A : DFA α σ) (w : List α) : Prop := ∀ q₁ q₂ : σ, A.evalFrom q₁ w = A.evalFrom q₂ w
See it in the graphDiscuss this resultChallenge it