AFTD Auto-Formalizing Theoretical Domains

cerny_swap_dfa

def

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

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