AFTD Auto-Formalizing Theoretical Domains

op_1667_opposite_cerny_product_two_is_synchronizing

theoremverified

The binary word [false, true] of length 2 synchronizes the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy C_2^swap.

Statement

theorem op_1667_opposite_cerny_product_two_is_synchronizing :
    dfa_is_synchronizing (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 2)) [false, true]
Source
folklore
Verified
14 Nov 2026
Axioms
Quot.soundpropext
Built on 5
  • 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…
  • nat_self_delimiting_code_fiveThe self-delimiting code of 5 (binary 101, least significant bit first 1,0,1) is true,true, true,false, true,true, false.
Used by 1

Read back from the Lean

The word [false, true] is a synchronizing word for the product DFA of cerny_dfa 2 and cerny_swap_dfa 2; that is, for every pair of states q₁, q₂ : Fin 2 × Fin 2, running the product automaton on the input sequence [false, true] from initial state q₁ yields the same final state as running it from q₂.

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 word [false, true] synchronizes the product automaton C₂ × C₂^swap by steering every state (q₁, q₂) ∈ {0, 1}² to (0, 1). The first symbol `false` increments q₁ modulo 2 while resetting q₂ to 0 (since C₂^swap negates the input symbol to `true`, which resets the state). The second symbol `true` resets the first component to 0 and increments the second component from 0 to 1. The formal proof unfolds the definitions and completes the finite state evaluation via simplification.

  1. The word [false, true] synchronizes the product automaton by mapping every state in Fin 2 × Fin 2 to (0, 1). automation

    Unfolding the definitions of `dfa_is_synchronizing`, `dfa_prod`, `cerny_dfa`, and `cerny_swap_dfa` reduces the goal to verifying that evaluating `[false, true]` from any initial state (q₁, q₂) in Fin 2 × Fin 2 yields the same destination state (0, 1). Lean's simplifier evaluates the transitions across all four possible states and closes the goal.

    line 3

    uses nat_self_delimiting_code_five

        dfa_is_synchronizing (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 2)) [false, true] := by first | exact nat_self_delimiting_code_five | (apply nat_self_delimiting_code_five <;> assumption) | (apply nat_self_delimiting_code_five <;> simp_all) | simpa using nat_self_delimiting_code_five | (simp only [dfa_is_synchronizing, dfa_prod, cerny_dfa, cerny_swap_dfa] at *; first | exact nat_self_delimiting_code_five | (apply nat_self_delimiting_code_five <;> assumption) | (apply nat_self_delimiting_code_five <;> simp_all) | simpa using nat_self_delimiting_code_five)
nat_self_delimiting_code_five
The self-delimiting binary encoding of 5 is [true, true, true, false, true, true, false].

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] synchronizes C_2 x C_2^swap. -/theorem op_1667_opposite_cerny_product_two_is_synchronizing :    dfa_is_synchronizing (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 2)) [false, true] := by first | exact nat_self_delimiting_code_five | (apply nat_self_delimiting_code_five <;> assumption) | (apply nat_self_delimiting_code_five <;> simp_all) | simpa using nat_self_delimiting_code_five | (simp only [dfa_is_synchronizing, dfa_prod, cerny_dfa, cerny_swap_dfa] at *; first | exact nat_self_delimiting_code_five | (apply nat_self_delimiting_code_five <;> assumption) | (apply nat_self_delimiting_code_five <;> simp_all) | simpa using nat_self_delimiting_code_five)
See it in the graphDiscuss this resultChallenge it