AFTD Auto-Formalizing Theoretical Domains

Cslib.Automata.NA.FinAcc.instAcceptor

instanceimported Lean

An NA.FinAcc accepts a string if there is a multistep transition from a start state to an accept state. This is the standard string recognition performed by NFAs in the literature.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.Automata Cslib.Automata.NA in
open Filter in
variable {State Symbol : Type*} in
@[simp, grind =]
instance Cslib.Automata.NA.FinAcc.instAcceptor : Acceptor (FinAcc State Symbol) Symbol
Defined in
CSLib, `Cslib.Automata.NA.FinAcc.instAcceptor`
Lean proof
By Fabrizio Montesi, Ching-Tsun Chou, Chris Henson, 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.
What was changed in Cslib.Automata.NA.FinAcc.instAcceptor
--- Cslib/Computability/Automata/NA/Basic.lean:59 ()
+++ as compiled here
@@ -1,7 +1,8 @@
-/-- An `NA.FinAcc` accepts a string if there is a multistep transition from a start state to an
-accept state.
-
-This is the standard string recognition performed by NFAs in the literature. -/
-@[simp, scoped grind =]
-instance : Acceptor (FinAcc State Symbol) Symbol where
+set_option autoImplicit true in
+set_option relaxedAutoImplicit true in
+open Cslib Cslib.Automata Cslib.Automata.NA in
+open Filter in
+variable {State Symbol : Type*} in
+@[simp, grind =]
+instance Cslib.Automata.NA.FinAcc.instAcceptor : Acceptor (FinAcc State Symbol) Symbol where
   Accepts (a : FinAcc State Symbol) (xs : List Symbol) :=
Verified
08 Oct 2026
Axioms
none listed
Built on 8

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.Automata Cslib.Automata.NA in
open Filter in
variable {State Symbol : Type*} in
/-- An `NA.FinAcc` accepts a string if there is a multistep transition from a start state to an accept state. This is the standard string recognition performed by NFAs in the literature. -/
@[simp, grind =]
instance Cslib.Automata.NA.FinAcc.instAcceptor : Acceptor (FinAcc State Symbol) Symbol where
  Accepts (a : FinAcc State Symbol) (xs : List Symbol) :=
    ∃ s ∈ a.start, ∃ s' ∈ a.accept, a.MTr s xs s'
See it in the graphDiscuss this resultChallenge it