My solution produces an automaton with 2n^2 + n states, but what is the smallest possible size? Is it still ~n^2?

Edited by author 14.02.2024 16:19

My solution produces an automaton with exactly 2n^2 + 1 states. Can it be done better? I don't know, but if I had to guess, I would say no.

However, for a particular input automaton, some of the states of the output automaton may be unaccessible, thus they could be removed and the problem could be solved with even fewer states. But, there are input automatons where all the states of the output automaton are accessible, thus the upper limit of my solution is 2n^2 + 1 states on the worst case.