AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_step

def

One 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 endmarker) apply δR and move to |w|, and at a position 1 ≤ i ≤ |w| read the symbol w_i and move by the direction δ gives. None when the transition is undefined.

Statement

def two_way_dfa_step {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (c : Q × ℕ) : Option (Q × ℕ)
Defined in
arXiv:2610.18897 (A factor-two lower bound for complementing two-way deterministic finite automata), Section 2.1: the tape positions 0, ..., t+1 with endmarkers at 0 and t+1, and the moves
Verified
23 Oct 2026
Axioms
none listed
Built on 1
  • two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…
Used by 7
  • two_way_dfa_runThe configuration after t steps of the computation from (s, 0) on w, or none once it has halted on an undefined transition.
  • two_way_dfa_halting_emptySanity: a two-state automaton with no transitions and s ≠ f halts on every input.
  • two_way_dfa_run_succFor any two-way deterministic finite automaton A, input word w, and time t, the configuration after t + 1 computation steps is the result…
  • two_way_dfa_step_rightSanity: on the right endmarker a step applies δR and moves to position |w|.
  • two_way_dfa_step_symbolSanity: at position i+1 ≤ |w| a step reads w_i and moves to i+2 or i.
  • two_way_dfa_accepts_of_s_eq_fSanity: if the initial state is the final state, every word is accepted (at time 0).
  • two_way_dfa_step_leftSanity: on the left endmarker a step applies δL and moves to position 1.

Lean source view module on GitHub

def two_way_dfa_step {σ Q : Type*} (A : two_way_dfa σ Q) (w : List σ) (c : Q × ℕ) : Option (Q × ℕ) :=
  if c.2 = 0 then (A.δL c.1).map (fun q => (q, 1))
  else if c.2 = w.length + 1 then (A.δR c.1).map (fun q => (q, w.length))
  else (w[c.2 - 1]?).bind (fun a =>
    (A.δ c.1 a).map (fun r => (r.1, if r.2 then c.2 + 1 else c.2 - 1)))
See it in the graphDiscuss this resultChallenge it