AFTD Auto-Formalizing Theoretical Domains

Cslib.Automata.DA.FinAcc.instAcceptor

instanceimported Lean

A DA.FinAcc accepts a string if its multistep transition function maps the start state and the string to an accept state. This is the standard string recognition performed by DFAs in the literature.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Filter in
open scoped Cslib.FLTS in
variable {State Symbol : Type*} in
@[simp, scoped grind =]
instance Cslib.Automata.DA.FinAcc.instAcceptor : Acceptor (DA.FinAcc State Symbol) Symbol
Defined in
CSLib, `Cslib.Automata.DA.FinAcc.instAcceptor`
Lean proof
By Fabrizio Montesi, Ching-Tsun Chou, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2025 Fabrizio Montesi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 5
  • Cslib.Automata.AcceptorAn Acceptor is a machine that recognises strings (lists of symbols in an alphabet).
  • Cslib.FLTS.mtrExtended transition function. Implementation note: compared to [Hopcroft2006], the definition consumes the input list of symbols from the…
  • Cslib.Automata.DA.FinAccA deterministic automaton that accepts finite strings (lists of symbols).
  • Cslib.Automata.DAA deterministic automaton extends a FLTS with a unique initial state.
  • Cslib.FLTSA Functional Labelled Transition System (FLTS) for a type of states (State) and a type of transition labels (Label) consists of a…
Used by 1

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Filter in
open scoped Cslib.FLTS in
variable {State Symbol : Type*} in
/-- A `DA.FinAcc` accepts a string if its multistep transition function maps the start state and the string to an accept state. This is the standard string recognition performed by DFAs in the literature. -/
@[simp, scoped grind =]
instance Cslib.Automata.DA.FinAcc.instAcceptor : Acceptor (DA.FinAcc State Symbol) Symbol where
  Accepts (a : DA.FinAcc State Symbol) (xs : List Symbol) :=
    a.mtr a.start xs ∈ a.accept
See it in the graphDiscuss this resultChallenge it