AFTD Auto-Formalizing Theoretical Domains

word_subtraction_step

def

The transition: push the new letter c onto the front of the buffer (shifting the rest right by one, dropping the oldest letter), shift the status bits up by one, and compute the new bit 0 as true iff some s in S is a suffix of the new word (read from the buffer) whose corresponding old prefix-status bit is false.

Statement

noncomputable def word_subtraction_step {α : Type*} (S : Finset (List α)) (n : ℕ) (hn : ∀ s ∈ S, s.length ≤ n) :
    (Fin n → Option α) × (Fin (n + 1) → Bool) → α → (Fin n → Option α) × (Fin (n + 1) → Bool)
Source
step towards word_subtraction_is_regular
Verified
09 Nov 2026
Axioms
none listed

Lean source view module on GitHub

/-- Transition function of the Theorem 2.9 automaton on state (buffer, status bits). -/
noncomputable def word_subtraction_step {α : Type*} (S : Finset (List α)) (n : ℕ) (hn : ∀ s ∈ S, s.length ≤ n) :
    (Fin n → Option α) × (Fin (n + 1) → Bool) → α → (Fin n → Option α) × (Fin (n + 1) → Bool) := fun st c =>
    let buf : Fin n → Option α :=
      fun i => if (i : ℕ) = 0 then some c else st.1 ⟨(i : ℕ) - 1, by have := i.isLt; omega⟩
    let b0 : Bool := by
      classical
      exact decide (∃ s, ∃ hs : s ∈ S,
        (∀ i : Fin s.length,
          buf ⟨(i : ℕ), by have := i.isLt; have := hn s hs; omega⟩ = s.reverse[(i : ℕ)]?)
        ∧ st.2 ⟨s.length - 1, by have := hn s hs; omega⟩ = false)
    (buf, fun j => if (j : ℕ) = 0 then b0 else st.2 ⟨(j : ℕ) - 1, by have := j.isLt; omega⟩)
See it in the graphDiscuss this resultChallenge it