Cslib.Automata.Acceptor.mem_language
theoremverifiedformalizationimported Lean
A string is in the language of an acceptor iff the acceptor accepts it.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in variable {Symbol : Type v} in @[simp, scoped grind =] theorem Cslib.Automata.Acceptor.mem_language [Acceptor A Symbol] (a : A) (xs : List Symbol) : xs ∈ language a ↔ Accepts a xs
- Formalizes
- CSLib, `Cslib.Automata.Acceptor.mem_language`
- Lean proof
- By Fabrizio Montesi, 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.Acceptor.mem_language← Cslib.Automata.Acceptor.mem_language (Cslib/Computability/Automata/Acceptors/Acceptor.lean:34): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 2
- Cslib.Automata.AcceptorAn
Acceptoris a machine that recognises strings (lists of symbols in an alphabet). - Cslib.Automata.Acceptor.languageThe language of an
Acceptoris the set of strings itAccepts.
- 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 variable {Symbol : Type v} in /-- A string is in the language of an acceptor iff the acceptor accepts it. -/ @[simp, scoped grind =] theorem Cslib.Automata.Acceptor.mem_language [Acceptor A Symbol] (a : A) (xs : List Symbol) : xs ∈ language a ↔ Accepts a xs := Iff.rfl