AFTD Auto-Formalizing Theoretical Domains

two_way_dfa

structure

A two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right (true)} on ordinary symbols, a partial transition δL(q) ∈ Q on the left endmarker (always moving right), a partial transition δR(q) ∈ Q on the right endmarker (always moving left), an initial state s and a final state f.

Statement

structure two_way_dfa (σ Q : Type*)
Defined in
arXiv:2610.18897 (A factor-two lower bound for complementing two-way deterministic finite automata), Section 2.1: the 2DFA (Q, Σ, δ, s, f), with the endmarker rows of δ split off as δL and δR so that their directions are built in
Verified
23 Oct 2026
Axioms
none listed
Used by 13
  • 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_mixed_count_leThe number of mixed states is at most the number of states.
  • 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_mixed_countb: the number of states that are targets of both a left-moving and a right-moving transition, endmarker transitions included, once the row…
  • 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_direction_determinateA is direction-determinate: some d : Q → {left, right} gives the direction of every defined transition from the state it enters, endmarker…
  • 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_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…
  • two_way_dfa_acceptsA accepts w when its computation from (s, 0) reaches the configuration (f, 0) (state f on the left endmarker). Infinite computations and…
  • two_way_dfa_haltingA is halting: on every input its computation stops, by an undefined transition or by reaching the accepting configuration (f, 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

structure two_way_dfa (σ Q : Type*) where
  δ : Q → σ → Option (Q × Bool)
  δL : Q → Option Q
  δR : Q → Option Q
  s : Q
  f : Q
See it in the graphDiscuss this resultChallenge it