OFFSET
0,2
COMMENTS
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
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
LINKS
M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007) 93-102, gives a(7) in Section 5.
Frederique Bassino, Julien David and Cyril Nicaud, REGAL: a library to randomly and exhaustively generate automata, also at HAL-00459643.
Michael Domaratzki, Derek Kisman, and Jeffrey Shalit. On the number of distinct languages accepted by finite automata with n states, Journal of Automata, Languages and Combinatorics 7 (2002) 4-18, Section 6, a(n) = f_2(n).
FORMULA
A059412(n) <= a(n). - Arthur O'Dwyer, Jul 26 2024
EXAMPLE
From Arthur O'Dwyer, Jul 26 2024: (Start)
For n=1 the a(1)=2 distinct DFAs are
State 1: a->1, b->1
State 1: a->1, b->1, accepting
The first of these accepts the empty language; the second accepts the universal language.
For n=3, the following two DFAs are equivalent, since they accept the same language:
State 1: a->2, b->2, accepting; State 2: a->1, b->3; State 3: a->2, b->2
State 1: a->3, b->3, accepting; State 2: a->3, b->3; State 3: a->1, b->2
The following DFA is not counted at all, because it is minimizable to (that is, accepts the same language as) a two-state DFA:
State 1: a->1, b->2; State 2: a->2, b->3, accepting; State 3: a->3, b->2, accepting
(End)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Johnicholas Hines (johnicholas.hines(AT)gmail.com), May 30 2007
EXTENSIONS
a(0)=0 and a(1)=2 prepended by Arthur O'Dwyer, Jul 26 2024
STATUS
approved