AFTD Auto-Formalizing Theoretical Domains

language_recognized_by_dfa_of_size_le

def

A language L is recognized by a deterministic finite automaton with at most k states.

Statement

def language_recognized_by_dfa_of_size_le {α : Type*} (L : Language α) (k : ℕ) : Prop
Defined in
arXiv:2611.09157 Problem 2.1
Verified
09 Nov 2026
Axioms
none listed

Read back from the Lean

For a type α, a language L : Language α, and a natural number k, language_recognized_by_dfa_of_size_le L k asserts that there exist a state type σ : Type, a Fintype σ instance, and a deterministic finite automaton M : DFA α σ such that the cardinality of σ is at most k and the language accepted by M is equal to L.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate that a language is recognized by a DFA with at most k states. -/
def language_recognized_by_dfa_of_size_le {α : Type*} (L : Language α) (k : ℕ) : Prop := ∃ (σ : Type) (_ : Fintype σ) (M : DFA α σ), Fintype.card σ ≤ k ∧ M.accepts = L
See it in the graphDiscuss this resultChallenge it