two_way_dfa_step_left
Sanity: on the left endmarker a step applies δL and moves to position 1.
Statement
theorem two_way_dfa_step_left {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (q : Q) : two_way_dfa_step A w (q, 0) = (A.δL q).map (fun q' => (q', 1))
- 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 theorem asserts that at the left endmarker (position 0), a two-way DFA transitions according to δL and moves the tape head to position 1. The proof proceeds by unfolding the definition of two_way_dfa_step, where the condition for being at position 0 holds trivially.
two_way_dfa_step A w (q, 0) = (A.δL q).map (fun q' => (q', 1))
Unfolding the definition of two_way_dfa_step on the configuration (q, 0), the condition c.2 = 0 is 0 = 0, which is true. The simplifier selects the first branch, which evaluates to (A.δL q).map (fun q' => (q', 1)), completing the proof.
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 (q, n), which branches on whether the tape head is at the left endmarker (position 0), the right endmarker, or an interior symbol of the input word.
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_left {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (q : Q) : two_way_dfa_step A w (q, 0) = (A.δL q).map (fun q' => (q', 1)) := by simp [two_way_dfa_step]