AFTD Auto-Formalizing Theoretical Domains

regular_word_subtraction_language

deforiginal

For each integer N ≥ 3, regular_word_subtraction_language N hN is the language over Bool accepted by the DFA with state set Fin (N + 1), start state 0, and sole accepting state 2, where letter false sends 0 to 2 and cyclically permutes 1 through N, and letter true sends 0 to 1, swaps 1 and 2, and fixes 3 through N.

Statement

def regular_word_subtraction_language (N : ℕ) (hN : 3 ≤ N) : Language Bool
Related work
arXiv:2611.09157
Verified
15 Nov 2026
Axioms
none listed

Read back from the Lean

The definition regular_word_subtraction_language takes a natural number N and a proof hN : 3 ≤ N, and defines a language over the alphabet Bool (i.e., a Set (List Bool)) as the language accepted by a deterministic finite automaton (DFA) with states Fin (N + 1): - **Start state:** 0 - **Accept states:** the singleton {2} - **Transition function** δ(q, c): - When c = false: - if q = 0, transition to 2 - else if q = N, transition to 1 - otherwise (0 < q < N), transition to q + 1 - When c = true: - if q = 0, transition to 1 - else if q = 1, transition to 2 - else if q = 2, transition to 1 - otherwise (q ≥ 3), transition to q (stay in the same state)

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 regular language accepted by the N-state binary DFA A_N of OP-1677. -/
def regular_word_subtraction_language (N : ℕ) (hN : 3 ≤ N) : Language Bool := (DFA.mk
  (fun (q : Fin (N + 1)) (c : Bool) =>
    match c with
    | false =>
      if h0 : q.val = 0 then ⟨2, by omega⟩
      else if hN_eq : q.val = N then ⟨1, by omega⟩
      else ⟨q.val + 1, by have := q.isLt; omega⟩
    | true =>
      if h0 : q.val = 0 then ⟨1, by omega⟩
      else if h1 : q.val = 1 then ⟨2, by omega⟩
      else if h2 : q.val = 2 then ⟨1, by omega⟩
      else q)
  ⟨0, by omega⟩
  {⟨2, by omega⟩}).accepts
See it in the graphDiscuss this resultChallenge it