• Theory of computation → Regular languages
  • Mathematics of computing → Enumeration
  • Mathematics of computing → Generating functions
Andrew Elvey Price
Université de Bordeaux, Laboratoire Bordelais de Recherche en Informatique, UMR 5800, 351 Cours de la Libération, 33405 Talence Cedex, France; Université de Tours, Institut Denis Poisson, UMR 7013, Parc de Grandmont, 37200 Tours, France
Wenjie Fang
Laboratoire d'Informatique Gaspard-Monge, UMR 8049, Université Gustave Eiffel, CNRS, ESIEE Paris, 77454 Marne-la-Vallée, France
Michael Wallner
Université de Bordeaux, Laboratoire Bordelais de Recherche en Informatique, UMR 5800, 351 Cours de la Libération, 33405 Talence Cedex, France; TU Wien, Institute for Discrete Mathematics and Geometry, Wiedner Hauptstrasse 8 - 10, 1040 Wien, Austria

Abstract. We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.