AFTD Auto-Formalizing Theoretical Domains

dfa_prod_is_synchronizing_iff

theoremverifiedformalization

A word w is synchronizing for the direct product dfa_prod A₁ A₂ of two deterministic finite automata if and only if w is synchronizing for both A₁ and A₂.

Statement

theorem dfa_prod_is_synchronizing_iff {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w : List α) : dfa_is_synchronizing (dfa_prod A₁ A₂) w ↔ dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w
Formalizes
arXiv:2611.09136 Lemma 3.1
Verified
09 Nov 2026
Axioms
none — Lean reports it depends on no axioms
Built on 2
  • 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…
Used by 5

Read back from the Lean

For any types α, σ₁, and σ₂, any deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂, and any word w : List α: w is a synchronizing word for the product automaton dfa_prod A₁ A₂ if and only if w is a synchronizing word for A₁ and w is a synchronizing word for 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

The equivalence is established in two directions using an auxiliary lemma showing that evaluation in the direct product DFA decomposes componentwise as `(dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w)`. For the forward direction, if the product automaton is synchronized by `w`, instantiating the synchronization condition on product states differing only in one coordinate and projecting yields that each factor automaton is synchronized. For the backward direction, if each factor is synchronized by `w`, evaluating from any two product states produces identical first components and identical second components, so the product states coincide.

  1. Evaluating a word on the direct product automaton acts componentwise on states: `(dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w)`.

    We prove this componentwise evaluation identity by induction on the word `w`, generalized over all state pairs `(q₁, q₂)`. The base case `w = []` holds by definition (`rfl`), as processing the empty word leaves any state unchanged. For the inductive step `a :: w`, unfolding `DFA.evalFrom` and list folding via `List.foldl_cons` rewrites the execution as a single transition step followed by evaluating `w`. The claim then follows by applying the induction hypothesis to the updated states `(A₁.step q₁ a, A₂.step q₂ a)`.

    lines 3–7

    uses DFA.evalFrom, List.foldl_cons

      induction w generalizing q₁ q₂ with
      | nil => rfl
      | cons a w ih =>
        simp only [DFA.evalFrom, List.foldl_cons]
        exact ih (A₁.step q₁ a) (A₂.step q₂ a)
  2. If the direct product automaton is synchronized by `w`, then the first automaton `A₁` is synchronized by `w`.

    We split the equivalence and assume that `w` synchronizes `dfa_prod A₁ A₂` (hypothesis `h`). To show that `A₁` is synchronized, let `q₁, q₂` be any two states of `A₁`. We instantiate hypothesis `h` on the product states `(q₁, A₂.start)` and `(q₂, A₂.start)`. Rewriting both sides with `dfa_prod_is_synchronizing_iff_evalFrom` gives `(A₁.evalFrom q₁ w, A₂.evalFrom A₂.start w) = (A₁.evalFrom q₂ w, A₂.evalFrom A₂.start w)`. Taking the first projection of both sides using `congrArg Prod.fst` yields `A₁.evalFrom q₁ w = A₁.evalFrom q₂ w`.

    lines 11–17

    uses dfa_prod_is_synchronizing_iff_evalFrom, congrArg, Prod.fst

      constructor
      · intro h
        constructor
        · intro q₁ q₂
          have hprod := h (q₁, A₂.start) (q₂, A₂.start)
          rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod
          exact congrArg Prod.fst hprod
  3. If the direct product automaton is synchronized by `w`, then the second automaton `A₂` is synchronized by `w`.

    To show that `A₂` is synchronized, let `q₁, q₂` be any two states of `A₂`. Symmetrically to the previous step, we instantiate the product synchronization hypothesis `h` on `(A₁.start, q₁)` and `(A₁.start, q₂)`. Rewriting with `dfa_prod_is_synchronizing_iff_evalFrom` and projecting onto the second coordinate using `congrArg Prod.snd` yields `A₂.evalFrom q₁ w = A₂.evalFrom q₂ w`.

    lines 18–21

    uses dfa_prod_is_synchronizing_iff_evalFrom, congrArg, Prod.snd

        · intro q₁ q₂
          have hprod := h (A₁.start, q₁) (A₁.start, q₂)
          rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod
          exact congrArg Prod.snd hprod
  4. If both `A₁` and `A₂` are synchronized by `w`, then the direct product automaton is synchronized by `w`.

    For the backward direction, assume `w` synchronizes `A₁` (hypothesis `h₁`) and `w` synchronizes `A₂` (hypothesis `h₂`). Given any two product states `(q₁, q₂)` and `(r₁, r₂)`, rewriting both sides of the product evaluation with `dfa_prod_is_synchronizing_iff_evalFrom` reduces the goal to showing `(A₁.evalFrom q₁ w, A₂.evalFrom q₂ w) = (A₁.evalFrom r₁ w, A₂.evalFrom r₂ w)`. By `Prod.ext`, this holds because `h₁ q₁ r₁` equates the first components and `h₂ q₂ r₂` equates the second components.

    lines 22–24

    uses dfa_prod_is_synchronizing_iff_evalFrom, Prod.ext

      · rintro ⟨h₁, h₂⟩ ⟨q₁, q₂⟩ ⟨r₁, r₂⟩
        rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom]
        exact Prod.ext (h₁ q₁ r₁) (h₂ q₂ r₂)
DFA.evalFrom
Evaluates a DFA on an input word starting from a given initial state by repeatedly applying its transition function.
List.foldl_cons
Folding a function over a non-empty list `a :: l` with accumulator `b` equals folding over `l` with accumulator `f b a`.
dfa_prod_is_synchronizing_iff_evalFrom
Evaluating the direct product automaton on a word `w` from initial state `(q₁, q₂)` produces the pair of states `(A₁.evalFrom q₁ w, A₂.evalFrom q₂ w)`.
congrArg
Applying a function `f` to equal arguments produces equal results (`a₁ = a₂ → f a₁ = f a₂`).
Prod.fst
The first projection of an ordered pair, mapping `(x, y)` to `x`.
Prod.snd
The second projection of an ordered pair, mapping `(x, y)` to `y`.
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.

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

lemma dfa_prod_is_synchronizing_iff_evalFrom {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (q₁ : σ₁) (q₂ : σ₂) (w : List α) :    (dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w) := by  induction w generalizing q₁ q₂ with  | nil => rfl  | cons a w ih =>    simp only [DFA.evalFrom, List.foldl_cons]    exact ih (A₁.step q₁ a) (A₂.step q₂ a)/-- A word synchronizes the direct product of two DFAs iff it synchronizes both DFAs. -/theorem dfa_prod_is_synchronizing_iff {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w : List α) : dfa_is_synchronizing (dfa_prod A₁ A₂) w ↔ dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := by  constructor  · intro h    constructor    · intro q₁ q₂      have hprod := h (q₁, A₂.start) (q₂, A₂.start)      rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod      exact congrArg Prod.fst hprod    · intro q₁ q₂      have hprod := h (A₁.start, q₁) (A₁.start, q₂)      rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod      exact congrArg Prod.snd hprod  · rintro ⟨h₁, h₂⟩ ⟨q₁, q₂⟩ ⟨r₁, r₂⟩    rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom]    exact Prod.ext (h₁ q₁ r₁) (h₂ q₂ r₂)
See it in the graphDiscuss this resultChallenge it