two_way_dfa_accepts_of_s_eq_f
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.
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).
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
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_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]⟩