|
| |
|
|
A129622
|
|
Number of minimal deterministic finite automata (DFA) with n states on a two-letter alphabet.
|
|
0
|
| |
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
