two_way_dfa_step_right
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.
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.
uses
two_way_dfa_stepsimp [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
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_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]