×

On the number of distinct languages accepted by finite automata with \(n\) states. (English) Zbl 1137.68421

Summary: 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.

MSC:

68Q45 Formal languages and automata
05A16 Asymptotic enumeration
68R05 Combinatorics in computer science
PDFBibTeX XMLCite