two_way_dfa_run_succ
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).
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.
dsimp [two_way_dfa_run]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.
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).
- The simplification step on line 4 (`dsimp [two_way_dfa_run]`) is formally redundant because `Function.iterate_succ_apply'` matches the goal definitionally; it is included in the formal proof to make the goal state readable.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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))