AFTD Auto-Formalizing Theoretical Domains

op_1670_opposite_cerny_product_two_three_is_synchronizing

theoremverified

The binary word [false, true, true, false] synchronizes the direct product dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) of the 2-state Černý automaton and the 3-state letter-swapped Černý automaton.

Statement

theorem op_1670_opposite_cerny_product_two_three_is_synchronizing :
    dfa_is_synchronizing (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3)) [false, true, true, false]
Source
arXiv:2611.09136, Shortest Synchronizing Words on Product Automata
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • cerny_dfaFor an integer n > 0, the Černý automaton C_n is the deterministic finite automaton with state set {0, ..., n-1} over the binary alphabet…
  • cerny_swap_dfaFor an integer n > 0, the letter-swapped Černý automaton C_n^swap is the deterministic finite automaton with state set {0, ..., n-1} where…
  • 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_synchronizingA word w : List α is synchronizing for a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all…
Used by 1

Read back from the Lean

The word [false, true, true, false] is a synchronizing word for the product DFA of the 2-state Černý automaton cerny_dfa 2 and the 3-state input-swapped Černý automaton cerny_swap_dfa 3. That is, for all states q₁ and q₂ in Fin 2 × Fin 3, executing the DFA on [false, true, true, false] from q₁ and from q₂ results in the same state.

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 proof unfolds the definition of a synchronizing word to obtain a universal condition over all pairs of states in the product DFA C₂ × C₃^swap. Because the state space is finite (with only 6 states), Lean checks the condition for all pairs by exhaustive computation (`decide`).

  1. To show that the word is synchronizing, it suffices to verify that feeding [false, true, true, false] sends every pair of states in Fin 2 × Fin 3 to the same state.

    Unfolding the definition of a synchronizing word (`dfa_is_synchronizing`) reduces the claim to showing that for all states q₁, q₂ in the product automaton, four consecutive transition steps under the symbols false, true, true, false result in the same state.

    line 4

    uses dfa_is_synchronizing

      dsimp [dfa_is_synchronizing]
  2. The word [false, true, true, false] synchronizes the product automaton. automation

    Since the state space Fin 2 × Fin 3 is finite (consisting of 2 × 3 = 6 states), whether all pairs transition to the same state is a finite, decidable condition that Lean verifies by exhaustive computation.

    line 5

      decide
dfa_is_synchronizing
A word w is synchronizing for a DFA if feeding w into any two states leads to the exact same final state.

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

/-- The word [false, true, true, false] of length 4 synchronizes C_2 × C_3^swap (OP-1670). -/theorem op_1670_opposite_cerny_product_two_three_is_synchronizing :    dfa_is_synchronizing (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3)) [false, true, true, false] := by  dsimp [dfa_is_synchronizing]  decide
See it in the graphDiscuss this resultChallenge it