AFTD Auto-Formalizing Theoretical Domains

dfa_prod_is_synchronizing_append

theoremverifiedformalization

If w₁ is a synchronizing word for A₁ and w₂ is a synchronizing word for A₂, then the concatenated word w₁ ++ w₂ is a synchronizing word for the direct product dfa_prod A₁ A₂.

Statement

theorem dfa_prod_is_synchronizing_append {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w₁ w₂ : List α) (hw₁ : dfa_is_synchronizing A₁ w₁) (hw₂ : dfa_is_synchronizing A₂ w₂) : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂)
Formalizes
arXiv:2611.09136 Lemma 3.3
Verified
09 Nov 2026
Axioms
Quot.soundpropext
Built on 3
  • 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…
  • dfa_prodThe direct product dfa_prod A₁ A₂ of two deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over alphabet α is the DFA…
  • dfa_prod_is_synchronizing_iffA word w is synchronizing for the direct product dfa_prod A₁ A₂ of two deterministic finite automata if and only if w is…
Used by 2

Read back from the Lean

For any alphabet type α and state types σ₁ and σ₂, let A₁ be a DFA over α with states σ₁ and A₂ be a DFA over α with states σ₂. Let w₁ and w₂ be words (List α). If w₁ is a synchronizing word for A₁ (that is, A₁.evalFrom q₁ w₁ = A₁.evalFrom q₂ w₁ for all states q₁, q₂ : σ₁) and w₂ is a synchronizing word for A₂ (that is, A₂.evalFrom q₁ w₂ = A₂.evalFrom q₂ w₂ for all states q₁, q₂ : σ₂), then the concatenation w₁ ++ w₂ is a synchronizing word for the product DFA dfa_prod A₁ A₂ (that is, (dfa_prod A₁ A₂).evalFrom p₁ (w₁ ++ w₂) = (dfa_prod A₁ A₂).evalFrom p₂ (w₁ ++ w₂) for all state pairs p₁, p₂ : σ₁ × σ₂).

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

To show that the concatenated word w₁ ++ w₂ synchronizes the product automaton A₁ × A₂, the proof verifies that any two initial state pairs (q₁, q₂) and (r₁, r₂) reach the same final state in each coordinate. Since product transitions act componentwise, evaluation of w₁ ++ w₂ decomposes into running w₁ followed by w₂ in each automaton. In the first component, w₁ already synchronizes A₁ to a common intermediate state, so the remaining word w₂ preserves equality. In the second component, regardless of the states reached after w₁, the suffix w₂ synchronizes A₂ to a common final state.

  1. To show that `w₁ ++ w₂` synchronizes the product automaton, it suffices to show that any two states transition to the same state in `A₁` and in `A₂` separately.

    By definition, a word synchronizes a DFA if running it from any two states yields the same final state. We introduce two arbitrary states `(q₁, q₂)` and `(r₁, r₂)` of the product automaton. Evaluating a word in the product DFA acts componentwise (`dfa_prod_is_synchronizing_iff_evalFrom`), transforming the equality of product evaluations into an equality of state pairs. Applying extensionality on pairs (`ext`) splits this into two subgoals: equality in the first component and equality in the second component.

    lines 3–5

    uses dfa_prod_is_synchronizing_iff_evalFrom

      intro ⟨q₁, q₂⟩ ⟨r₁, r₂⟩
      rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom]
      ext
  2. The first component DFA `A₁` reaches the same state from `q₁` and `r₁` after reading `w₁ ++ w₂`.

    Simplifying the first projection, we must show `A₁.evalFrom q₁ (w₁ ++ w₂) = A₁.evalFrom r₁ (w₁ ++ w₂)`. The evaluation of the concatenated word `w₁ ++ w₂` splits into evaluating `w₁` followed by `w₂` (`DFA.evalFrom_of_append`). Since `w₁` synchronizes `A₁` (hypothesis `hw₁`), running `w₁` from `q₁` and `r₁` reaches the same intermediate state in `A₁`. Consequently, running `w₂` from identical intermediate states yields identical final states.

    lines 6–7

    uses DFA.evalFrom_of_append

      · dsimp
        rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append, hw₁ q₁ r₁]
  3. The second component DFA `A₂` reaches the same state from `q₂` and `r₂` after reading `w₁ ++ w₂`.

    Simplifying the second projection, we must show `A₂.evalFrom q₂ (w₁ ++ w₂) = A₂.evalFrom r₂ (w₁ ++ w₂)`. As before, evaluating `w₁ ++ w₂` decomposes into running `w₁` to intermediate states `A₂.evalFrom q₂ w₁` and `A₂.evalFrom r₂ w₁`, followed by running `w₂` (`DFA.evalFrom_of_append`). Since `w₂` synchronizes `A₂` (hypothesis `hw₂`), running `w₂` from any two states—in particular, these two intermediate states—ends in the same state in `A₂`.

    lines 8–9

    uses DFA.evalFrom_of_append

      · dsimp
        rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append, hw₂ (A₂.evalFrom q₂ w₁) (A₂.evalFrom r₂ w₁)]
dfa_prod_is_synchronizing_iff_evalFrom
Evaluating a word in a product DFA from a pair of states is the pair of states reached by evaluating the word in each component DFA independently.
DFA.evalFrom_of_append
Evaluating a concatenated word `x ++ y` from a state in a DFA is equal to evaluating `y` starting from the state reached after evaluating `x`.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Concatenation of synchronizing words for two DFAs synchronizes their direct product. -/theorem dfa_prod_is_synchronizing_append {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w₁ w₂ : List α) (hw₁ : dfa_is_synchronizing A₁ w₁) (hw₂ : dfa_is_synchronizing A₂ w₂) : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) := by  intro ⟨q₁, q₂⟩ ⟨r₁, r₂⟩  rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom]  ext  · dsimp    rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append, hw₁ q₁ r₁]  · dsimp    rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append, hw₂ (A₂.evalFrom q₂ w₁) (A₂.evalFrom r₂ w₁)]
See it in the graphDiscuss this resultChallenge it