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.Cslib.Automata.DA.FinAcc.instAcceptor← @Cslib/Computability/Automata/DA/Basic.lean:84 (Cslib/Computability/Automata/DA/Basic.lean:79): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 5
- Cslib.Automata.AcceptorAn
Acceptoris 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
FLTSwith 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…
- Cslib.Automata.AcceptorAn
- Used by 1
- Cslib.Automata.NA.FinAcc.instAcceptorAn
NA.FinAccaccepts a string if there is a multistep transition from a start state to an accept state. This is the standard string…
- Cslib.Automata.NA.FinAcc.instAcceptorAn
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