AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_step_right

theoremverified

Sanity: on the right endmarker a step applies δR and moves to position |w|.

Statement

theorem two_way_dfa_step_right {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (q : Q) :
    two_way_dfa_step A w (q, w.length + 1) = (A.δR q).map (fun q' => (q', w.length))
Source
sanity lemma for two_way_dfa_step
Verified
23 Oct 2026
Axioms
propext
Built on 2
  • two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…
  • 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…

The proof, explained

The proof evaluates the transition function two_way_dfa_step on the configuration at the right endmarker, where the head is at position |w| + 1. Unfolding two_way_dfa_step, the first branch condition |w| + 1 = 0 is false and the second condition |w| + 1 = |w| + 1 is trivially true. Simplification reduces the step directly to the right-hand side.

  1. two_way_dfa_step A w (q, |w| + 1) = (A.δR q).map (fun q' => (q', |w|)) automation

    Unfolding the definition of two_way_dfa_step at configuration (q, |w| + 1), the first branch checks whether |w| + 1 = 0, which is false since |w| + 1 ≥ 1. The second branch checks whether |w| + 1 = |w| + 1, which holds reflexively. The simplifier evaluates these conditions and reduces the expression to the right endmarker branch, matching the right-hand side.

    line 3

    uses two_way_dfa_step

      simp [two_way_dfa_step]
two_way_dfa_step
the single-step transition function of a two-way DFA on a configuration (state, position), which handles the left endmarker at position 0, the right endmarker at position |w| + 1, and the input symbols in between

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

theorem two_way_dfa_step_right {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (q : Q) :    two_way_dfa_step A w (q, w.length + 1) = (A.δR q).map (fun q' => (q', w.length)) := by  simp [two_way_dfa_step]
See it in the graphDiscuss this resultChallenge it