The Maximum State Complexity for Finite Languages

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.