cerny_swap_dfa
For an integer n > 0, the letter-swapped Černý automaton C_n^swap is the deterministic finite automaton with state set {0, ..., n-1} where the transitions for false and true are exchanged relative to C_n.
Statement
def cerny_swap_dfa (n : ℕ) (hn : 0 < n := by omega) : DFA Bool (Fin n)
- Defined in
- Jan Černý (1964); arXiv:2611.09136
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Used by 4
- op_1670_opposite_cerny_product_two_three_is_synchronizingThe binary word [false, true, true, false] synchronizes the direct product dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) of the 2-state Černý…
- op_1670_opposite_cerny_product_reset_threshold_two_threeThe reset threshold of the direct product dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) of the 2-state Černý automaton and the 3-state…
- op_1667_opposite_cerny_product_two_is_synchronizingThe binary word [false, true] of length 2 synchronizes the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy…
- 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
Given a natural number $n$ and a proof $hn : 0 < n$ (defaulting to by omega), cerny_swap_dfa n hn defines a deterministic finite automaton (DFA Bool (Fin n)) with input alphabet Bool and state type Fin n. Its components are:
- step: the transition function that takes a state $x \in \mathrm{Fin}\ n$ and an input symbol $b : \mathrm{Bool}$. Because it matches on !b:
- When $b = \mathrm{true}$ (so !b = false), it transitions to state $(x.val + 1) \pmod n$.
- When $b = \mathrm{false}$ (so !b = true), it transitions to state $0$ if $x.val = n - 1$, and otherwise stays at state $x$.
- start: the initial state $0 \in \mathrm{Fin}\ n$.
- accept: the empty set $\emptyset$ of accepting states.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The letter-swapped Černý automaton C_n^swap where the roles of false and true are exchanged. -/ def cerny_swap_dfa (n : ℕ) (hn : 0 < n := by omega) : DFA Bool (Fin n) where step := fun x b => match !b with | false => ⟨(x.val + 1) % n, Nat.mod_lt _ hn⟩ | true => if x.val = n - 1 then ⟨0, hn⟩ else x start := ⟨0, hn⟩ accept := ∅