dfa_prod_is_synchronizing_append
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 automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all… - dfa_prodThe direct product
dfa_prod A₁ A₂of two deterministic finite automataA₁ : DFA α σ₁andA₂ : DFA α σ₂over alphabetαis the DFA… - dfa_prod_is_synchronizing_iffA word
wis synchronizing for the direct productdfa_prod A₁ A₂of two deterministic finite automata if and only ifwis…
- dfa_is_synchronizingA word
- Used by 2
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
A₁andA₂over a common alphabet, the direct product attains the lower bound… - dfa_prod_reset_threshold_boundsFor any two deterministic finite automata
A₁andA₂over the same alphabet, the reset threshold of their direct product satisfies…
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
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.
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.
uses
dfa_prod_is_synchronizing_iff_evalFromintro ⟨q₁, q₂⟩ ⟨r₁, r₂⟩ rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] ext
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.
uses
DFA.evalFrom_of_append· dsimp rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append, hw₁ q₁ r₁]
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₂`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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₁)]