cerny_dfa
For an integer n > 0, the Černý automaton C_n is the deterministic finite automaton with state set {0, ..., n-1} over the binary alphabet {false, true}, where letter false acts by cyclic increment x ↦ (x + 1) mod n, and letter true fixes 0, ..., n-2 while mapping n-1 to 0.
Statement
def cerny_dfa (n : ℕ) (hn : 0 < n := by omega) : DFA Bool (Fin n)
- Defined in
- Jan Černý, "Poznámka k homogénnym experimentom s konečnými automatmi", Mat.-Fyz. Čas. SAV 14 (1964), 208-216
- 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 (with default proof by omega), cerny_dfa n hn defines a deterministic finite automaton (DFA Bool (Fin n)) with input alphabet Bool and state type Fin n having:
- transition function step x b:
- if b = false, the next state is ⟨(x.val + 1) % n, _⟩;
- if b = true, the next state is ⟨0, hn⟩ if x.val = n - 1, and x otherwise;
- start state start: ⟨0, hn⟩ (state 0);
- accepting states accept: the empty set ∅.
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 n-state Černý automaton C_n over binary alphabet Bool = {false, true}, where false cyclically increments states modulo n and true maps n-1 to 0 while fixing other states. -/ def cerny_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 := ∅