cp's OEIS Frontend

A129622 Number of minimal deterministic finite automata (DFA) with n states on a two-letter alphabet.

%I A129622 #34 Jul 31 2024 11:52:18
%S A129622 0,2,24,1028,56014,3705306,286717796,25493886852
%N A129622 Number of minimal deterministic finite automata (DFA) with n states on a two-letter alphabet.
%C A129622 DFAs are counted up to equivalence, where two DFAs are equivalent if they recognize the same language. Therefore, a(n) is the number of languages on {a,b} recognizable by a minimal complete DFA of n states. A minimal DFA is one which is not equivalent to any smaller DFA. - _Arthur O'Dwyer_, Jul 26 2024
%C A129622 A DFA requires at least one state: the initial state. Since there are no DFAs with zero states, a(0)=0. - _Arthur O'Dwyer_, Jul 26 2024
%H A129622 M. Almeida, N. Moreira, and R. Reis, <a href="http://dx.doi.org/10.1016/j.tcs.2007.07.029">Enumeration and generation with a string automata representation</a>, Theor. Comp. Sci. 387 (2007) 93-102, gives a(7) in Section 5.
%H A129622 Frederique Bassino, Julien David and Cyril Nicaud, <a href="http://igm.univ-mlv.fr/~jdavid01/Publications.php">REGAL: a library to randomly and exhaustively generate automata</a>, also at <a href="https://hal.science/hal-00459643">HAL-00459643</a>.
%H A129622 Michael Domaratzki, Derek Kisman, and Jeffrey Shalit. <a href="https://doi.org/10.25596/jalc-2002-469">On the number of distinct languages accepted by finite automata with n states</a>, Journal of Automata, Languages and Combinatorics 7 (2002) 4-18, Section 6, a(n) = f_2(n).
%F A129622 A059412(n) <= a(n). - _Arthur O'Dwyer_, Jul 26 2024
%e A129622 From _Arthur O'Dwyer_, Jul 26 2024: (Start)
%e A129622 For n=1 the a(1)=2 distinct DFAs are
%e A129622   State 1: a->1, b->1
%e A129622   State 1: a->1, b->1, accepting
%e A129622 The first of these accepts the empty language; the second accepts the universal language.
%e A129622 For n=3, the following two DFAs are equivalent, since they accept the same language:
%e A129622   State 1: a->2, b->2, accepting; State 2: a->1, b->3; State 3: a->2, b->2
%e A129622   State 1: a->3, b->3, accepting; State 2: a->3, b->3; State 3: a->1, b->2
%e A129622 The following DFA is not counted at all, because it is minimizable to (that is, accepts the same language as) a two-state DFA:
%e A129622   State 1: a->1, b->2; State 2: a->2, b->3, accepting; State 3: a->3, b->2, accepting
%e A129622 (End)
%Y A129622 Cf. A059412, A000282.
%K A129622 nonn,more
%O A129622 0,2
%A A129622 Johnicholas Hines (johnicholas.hines(AT)gmail.com), May 30 2007
%E A129622 a(0)=0 and a(1)=2 prepended by _Arthur O'Dwyer_, Jul 26 2024