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

[Arthur O'Dwyer]

On Wed, Jul 24, 2024 at 12:37 PM brad klee <bradklee at proton.me> wrote:

>
> What's more interesting to me as a result of this recent
> experiment is how many different equivalent regex's can
> describe the same DFA-produced regular language.
>
> In the continuation, I'm curious about algorithms that
> compare and reduce regex over finite alphabets. Would
> be nice to know more about that...


Here is some material on converting DFAs to minimal regexes, but I haven't
read it all yet:
https://stackoverflow.com/questions/35112630/minimize-specific-regular-expression
https://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions

Here is my code for counting languages recognizable by n-state DFAs (in
Python and as of a few minutes ago also in much faster C++):
https://github.com/Quuxplusone/RecreationalMath/tree/master/CountDFAs

a(0) = 0
a(1) = 1
a(2) = 13
a(3) = 527
a(4) = 28534
a(5) = 1881187

The C++ can compute a(5) in about 20 seconds on my MacBook Pro (using five
threads).
But each subsequent a(n) requires testing each of O(n^{2n+1}) candidate
DFAs on O(2^{2n}) input strings, so computing a(6) by this method would
take a week or two, and this approach won't work for a(7) at all. Some
smarter approach will be needed.

Cheers,
Arthur