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

0, 2, 24, 1028, 56014, 3705306, 286717796, 25493886852

Offset: 0

Author

Johnicholas Hines (johnicholas.hines(AT)gmail.com), May 30 2007

Keywords

• nonn
• more

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

Examples

			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)
		

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).

Crossrefs

Cf. A059412, A000282.

Formula

A059412(n) <= a(n). - Arthur O'Dwyer, Jul 26 2024

Extensions

a(0)=0 and a(1)=2 prepended by Arthur O'Dwyer, Jul 26 2024