AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_run_succ

theoremverified

For any two-way deterministic finite automaton A, input word w, and time t, the configuration after t + 1 computation steps is the result of applying one transition step to the configuration at time t.

Statement

theorem two_way_dfa_run_succ {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (t : ℕ) :
    two_way_dfa_run A w (t + 1) = (two_way_dfa_run A w t).bind (two_way_dfa_step A w)
Source
arXiv:2610.18897
Verified
24 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • two_way_dfa_runThe configuration after t steps of the computation from (s, 0) on w, or none once it has halted on an undefined transition.
  • two_way_dfa_stepOne step on the input w: in configuration (q, i), at position 0 (left endmarker) apply δL and move to 1, at position |w|+1 (right…
  • two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…

Read back from the Lean

For all types σ and Q, every two-way deterministic finite automaton A : two_way_dfa σ Q, every input list w : List σ, and every natural number t : ℕ, the configuration after t + 1 steps (two_way_dfa_run A w (t + 1)) equals the monadic bind of the single-step transition function two_way_dfa_step A w over the configuration after t steps (two_way_dfa_run A w t).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, the configuration of a two-way DFA after t steps is the t-fold iteration of the monadic single-step transition function starting from the initial state at position 0. The assertion that t + 1 steps equals one step applied to the result after t steps is therefore an immediate instance of the iteration identity f^[t + 1] x = f (f^[t] x).

  1. Unfolding the definition of `two_way_dfa_run` expresses both sides in terms of iterated function application.

    By definition, `two_way_dfa_run A w t` is the t-fold iteration of the transition map c ↦ c.bind (two_way_dfa_step A w) starting from the initial configuration some (A.s, 0). Expanding this definition exposes the fact that the left-hand side is the (t + 1)-fold iterate, while the right-hand side is one additional transition applied to the t-fold iterate.

    line 4

      dsimp [two_way_dfa_run]
  2. The goal matches the standard recurrence relation f^[t + 1] x = f (f^[t] x) for function iteration.

    Applying the general lemma `Function.iterate_succ_apply'` to the step transition function f(c) = c.bind (two_way_dfa_step A w), step count t, and initial configuration x = some (A.s, 0) completes the proof.

    line 5

    uses Function.iterate_succ_apply'

      exact Function.iterate_succ_apply' (fun c => c.bind (two_way_dfa_step A w)) t (some (A.s, 0))
Function.iterate_succ_apply'
For any function f, natural number n, and point x, the (n + 1)-st iterate of f on x equals f applied to the n-th iterate of f on x: f^[n + 1] x = f (f^[n] x).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The configuration of a 2DFA after t + 1 steps is obtained by applying one step to the configuration after t steps. -/theorem two_way_dfa_run_succ {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (t : ℕ) :    two_way_dfa_run A w (t + 1) = (two_way_dfa_run A w t).bind (two_way_dfa_step A w) := by  dsimp [two_way_dfa_run]  exact Function.iterate_succ_apply' (fun c => c.bind (two_way_dfa_step A w)) t (some (A.s, 0))
See it in the graphDiscuss this resultChallenge it