On the Number of Distinct Languages Accepted by Finite Automata with n States

Abstract

We give asymptotic estimates and some explicit computations for both the number of distinct languages and the number of distinct finite languages over a $k$-letter alphabet that are accepted by deterministic finite automata (resp. nondeterministic finite automata) with $n$ states.