AFTD Auto-Formalizing Theoretical Domains

dfa_prod_is_synchronizing_of_subset_synchronizing

theoremverifiedformalization

If w₁ is a synchronizing word for A₁, and v is a subset-synchronizing word for the image set of w₁ on A₂, then the concatenated word w₁ ++ v is a synchronizing word for the direct product dfa_prod A₁ A₂.

Statement

theorem dfa_prod_is_synchronizing_of_subset_synchronizing {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w₁ v : List α) (hw₁ : dfa_is_synchronizing A₁ w₁) (hv : dfa_is_subset_synchronizing A₂ (Set.range (fun q : σ₂ => A₂.evalFrom q w₁)) v) : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ v)
Formalizes
arXiv:2611.09136 Sec. 7
Verified
09 Nov 2026
Axioms
Quot.soundpropext
Built on 4
  • 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_is_subset_synchronizingA word w : List α is subset-synchronizing for a subset S : Set σ of states of a deterministic finite automaton A : DFA α σ if…
  • 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 1

Read back from the Lean

For any alphabet type α and state types σ₁ and σ₂, let A₁ be a DFA over α with state type σ₁, let A₂ be a DFA over α with state type σ₂, and let w₁ and v be lists of symbols in α (words). If w₁ is a synchronizing word for A₁, and v is a subset-synchronizing word for A₂ on the subset of states consisting of the image (range) of σ₂ under evaluation of w₁ (i.e., { A₂.evalFrom q w₁ | q : σ₂ }), then the concatenated word w₁ ++ v is a synchronizing word for the product DFA dfa_prod A₁ A₂.

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 prove that w₁ ++ v is synchronizing for the direct product A₁ × A₂, we consider two arbitrary states (q₁, q₂) and (r₁, r₂) and show component-wise that they reach the same destination. In the first component, reading w₁ immediately synchronizes q₁ and r₁ to the same state in A₁ because w₁ is synchronizing, so reading v keeps them identical. In the second component, reading w₁ maps both states into the image set of w₁, which is then brought to a single state in A₂ by v because v is subset-synchronizing for that image.

  1. To show that w₁ ++ v synchronizes the product DFA, it suffices to show that for any two initial states (q₁, q₂) and (r₁, r₂), both component DFAs reach the same final state after reading w₁ ++ v.

    A word synchronizes an automaton if it sends every pair of states to the same destination. We introduce two arbitrary states (q₁, q₂) and (r₁, r₂) of the product automaton (line 3). Since evaluation on a product DFA decomposes component-wise (by dfa_prod_is_synchronizing_iff_evalFrom on line 4), the state reached in the product DFA is the pair of states reached in A₁ and A₂. Using extensionality on pairs (ext on line 5), the goal splits into verifying equality for the first component and the second component separately.

    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 automaton A₁ reaches the same state from q₁ and r₁: A₁.evalFrom q₁ (w₁ ++ v) = A₁.evalFrom r₁ (w₁ ++ v).

    Simplifying the first projection (line 6) leaves the equality in A₁. By DFA.evalFrom_of_append, running the concatenated word w₁ ++ v is equivalent to running w₁ first and then running v from the resulting state. Since w₁ is synchronizing for A₁ (hw₁), the states reached after w₁ are identical (A₁.evalFrom q₁ w₁ = A₁.evalFrom r₁ w₁), so running v afterwards leaves them equal as well.

    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 automaton A₂ reaches the same state from q₂ and r₂: A₂.evalFrom q₂ (w₁ ++ v) = A₂.evalFrom r₂ (w₁ ++ v).

    Simplifying the second projection (line 8) isolates the execution in A₂. Rewriting with DFA.evalFrom_of_append (line 9) splits the word w₁ ++ v into w₁ followed by v. The intermediate states A₂.evalFrom q₂ w₁ and A₂.evalFrom r₂ w₁ both belong to the image set of w₁ on A₂ by Set.mem_range_self. Since v is subset-synchronizing for this image set (hv), running v from these two intermediate states yields the same final state, closing the goal (line 10).

    lines 8–10

    uses DFA.evalFrom_of_append, Set.mem_range_self

      · dsimp
        rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append]
        exact hv _ (Set.mem_range_self q₂) _ (Set.mem_range_self r₂)
dfa_prod_is_synchronizing_iff_evalFrom
Evaluating a word from a state pair in the direct product DFA equals 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 starting state is equal to evaluating x from that start state, and then evaluating y from the resulting state.
Set.mem_range_self
For any function f and input i, the value f(i) belongs to the range of f.

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

/-- Concatenating a synchronizing word for A₁ with a word that subset-synchronizes its image in A₂ yields a synchronizing word for the direct product. -/theorem dfa_prod_is_synchronizing_of_subset_synchronizing {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w₁ v : List α) (hw₁ : dfa_is_synchronizing A₁ w₁) (hv : dfa_is_subset_synchronizing A₂ (Set.range (fun q : σ₂ => A₂.evalFrom q w₁)) v) : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ v) := 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]    exact hv _ (Set.mem_range_self q₂) _ (Set.mem_range_self r₂)
See it in the graphDiscuss this resultChallenge it