The Maximum State Complexity for Finite Languages
Cezar Câmpeanu, Wing Hong Ho · Journal of automata, languages and combinatorics · 2004
A measure of the complexity of a regular language $L$ is the number of states in the smallest DFA accepting $L$. We study this quantity in the case of finite languages over a non-unary alphabet. We compute the maximum number of states of a minimal deterministic finite automaton (DFA) recognizing words of length less than or equal to some given integer. We also compute the maximum number of states of a minimal complete DFA that accepts only words of length equal to a given integer. For both cases, we prove that the upper bound can be reached by an explicit construction of a DFA, and we compute the asymptotic behavior of the upper bound.