AFTD Auto-Formalizing Theoretical Domains

cerny_dfa

def

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

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 := ∅
See it in the graphDiscuss this resultChallenge it