op_1667_opposite_cerny_product_two_is_synchronizing
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 automataA₁ : DFA α σ₁andA₂ : DFA α σ₂over alphabetαis the DFA… - dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor 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
- op_1667_opposite_cerny_product_reset_threshold_twoThe reset threshold of the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy C_2^swap is 2.
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.
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.
uses
nat_self_delimiting_code_fivedfa_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].
- The proof line consists of an automated search fallback sequence (`first | ...`). The lemma `nat_self_delimiting_code_five` is passed to `simpa` as an artifact of that search, but is unused; simplification alone closes the finite state evaluation.
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.
/-- 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)