two_way_dfa_step_symbol
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.
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.
have h1 : i ≠ w.length := hi.neThe 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.
uses
List.getElem?_eq_getElemsimp [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].
- In this formalization of a two-way DFA, tape positions are 1-indexed with respect to the input word: position 0 is reserved for the left endmarker, positions 1 through |w| correspond to list indices 0 through |w| - 1, and position |w| + 1 corresponds to the right endmarker.
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.
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]