AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_step_left

theoremverified

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.

  1. 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.

    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 (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

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]
See it in the graphDiscuss this resultChallenge it