[seqfan] Re: A new sequence counting the number of distinct languages recognized by DFAs

[Thomas Baruchel]

On Mon, 22 Jul 2024, Arthur O'Dwyer wrote:
> Re: a(0), I think you need to nail down more precisely what you mean by "a
> DFA with n states." If you mean that you can draw it with n little circular
> "spots", plus arrows leading off-screen to "accept" and/or "reject"
> outcomes, then a(0) is obviously at least 2:
> - no spots, just an arrow labeled "accept" [the universal language]
> - no spots, just an arrow labeled "reject" [the empty language]
> But normally, I think, the best way to count n-state DFAs is to require
> every state to be "on-screen," and never let the cursor escape the system —
> make it a completely closed system — and just label some set of "spots"
> themselves as "accepting". So your five automata above would be represented

Hi, thank you for your answer and suggestions; I should indeed have
explained more precisely that my DFAs rely on partial transition
functions. When computing the terms of this sequence, I have to make
the diagram complete (by adding an extra state if required) in order
to make some operations easier, but I chose partial transition functions
on purpose, hence the difference between your values and mine.

The exact definition I rely on is described in the following terms
on Wikipedia:

" While this is the most common definition, some authors use the term
deterministic finite automaton for a slightly different notion: an
automaton that defines at most one transition for each state and each
input symbol; the transition function is allowed to be partial.[5] When
no transition is defined, such an automaton halts. "
(Source:
https://en.wikipedia.org/wiki/Deterministic_finite_automaton#Complete_and_incomplete
)

Best regards,

--
Thomas Baruchel