AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_step_symbol

theoremverified

Sanity: at position i+1 ≤ |w| a step reads w_i and moves to i+2 or i.

Statement

theorem two_way_dfa_step_symbol {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (q : Q) (i : ℕ)
    (hi : i < w.length) :
    two_way_dfa_step A w (q, i + 1) =
      (A.δ q w[i]).map (fun r => (r.1, if r.2 then i + 2 else i))
Source
sanity lemma for two_way_dfa_step
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
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

This lemma verifies that when a two-way DFA is at an internal tape position i + 1 (with i < |w|), its step function reads the symbol w[i] and transitions normally rather than encountering an endmarker. Because i < |w|, the head is at neither the left endmarker (position 0) nor the right endmarker (position |w| + 1). Unfolding two_way_dfa_step and resolving the list lookup w[i]? to some w[i] simplifies the next configuration to the state and direction specified by A.δ q w[i], with the position updated to i + 2 or i.

  1. i ≠ |w|

    Because i < |w| by hypothesis (hi), i cannot equal |w|. This is established to ensure that the current head position i + 1 does not coincide with the right endmarker at |w| + 1.

    line 5

      have h1 : i ≠ w.length := hi.ne
  2. The step from configuration (q, i + 1) applies the transition function δ to q and w[i], updating the position to i + 2 on a right move or i on a left move.

    Unfolding two_way_dfa_step, the position i + 1 is neither 0 (the left endmarker) nor |w| + 1 (the right endmarker, by h1). The definition falls through to reading the symbol at index (i + 1) - 1 = i. By List.getElem?_eq_getElem, w[i]? evaluates to some w[i]. The transition δ(q, w[i]) is executed: moving right (r.2 = true) advances the head to (i + 1) + 1 = i + 2, while moving left (r.2 = false) moves it to (i + 1) - 1 = i. The simp tactic applies these simplifications and closes the goal.

    line 6

    uses List.getElem?_eq_getElem

      simp [two_way_dfa_step, h1, List.getElem?_eq_getElem hi]
List.getElem?_eq_getElem
If an index i is strictly less than the length of a list l, then the safe lookup l[i]? returns some l[i].

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_symbol {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (q : Q) (i : ℕ)    (hi : i < w.length) :    two_way_dfa_step A w (q, i + 1) =      (A.δ q w[i]).map (fun r => (r.1, if r.2 then i + 2 else i)) := by  have h1 : i ≠ w.length := hi.ne  simp [two_way_dfa_step, h1, List.getElem?_eq_getElem hi]
See it in the graphDiscuss this resultChallenge it