The State Complexity of Lexicographically Smallest Words and Computing Successors

Given a regular language L over an ordered alphabet [Formula: see text], the set of lexicographically smallest (resp., largest) words of each length is itself regular. Moreover, there exists an unambiguous finite-state transducer that, on a given word [Formula: see text], outputs the length-lexicographically smallest word larger than w (henceforth called the L-successor of w). In both cases, naïve constructions result in an exponential blowup in the number of states. We prove that if L is recognized by a DFA with n states, then [Formula: see text] states are sufficient for a DFA to recognize the subset S(L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S(L) is represented as an NFA. We then show that the same upper and lower bounds hold for an unambiguous finite-state transducer that computes L-successors.