AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_accepts_of_s_eq_f

theoremverified

Sanity: if the initial state is the final state, every word is accepted (at time 0).

Statement

theorem two_way_dfa_accepts_of_s_eq_f {σ Q : Type*} (A : two_way_dfa σ Q) (h : A.s = A.f)
    (w : List σ) : two_way_dfa_accepts A w
Source
sanity lemma for two_way_dfa_accepts
Verified
23 Oct 2026
Axioms
propext
Built on 4
  • 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…
  • 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_runThe configuration after t steps of the computation from (s, 0) on w, or none once it has halted on an undefined transition.

The proof, explained

A two-way DFA accepts an input word if it reaches its final state at head position 0 after some number of steps t. When the initial state coincides with the final state (A.s = A.f), the machine already satisfies this acceptance condition at time t = 0 without taking any steps. Hence, every word is accepted immediately.

  1. The DFA accepts w at time t = 0.

    By definition, the DFA accepts w if there exists a time t at which the configuration is (A.f, 0). At t = 0, no steps have been executed, so the machine is in its initial configuration (A.s, 0). Since the initial state equals the final state (A.s = A.f by h), this configuration is already (A.f, 0).

    line 3

    uses two_way_dfa_run

      ⟨0, by simp [two_way_dfa_run, h]⟩
two_way_dfa_run
The configuration of the two-way DFA on input word w after t steps, starting at (s, 0).

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_accepts_of_s_eq_f {σ Q : Type*} (A : two_way_dfa σ Q) (h : A.s = A.f)    (w : List σ) : two_way_dfa_accepts A w :=  ⟨0, by simp [two_way_dfa_run, h]⟩
See it in the graphDiscuss this resultChallenge it