On the boundary of regular languages (Q2344745)

This paper considers the computation of the boundary of a regular language, defined as the intersection of the Kleene star of this language with the Kleene star of its complement. The precise state complexity of the boundary of a regular language is found. The upper bound is obtained by counting unreachable states in the automaton produced using standard constructions for Kleene star and intersection, and it is proved that this upper bound can be reached by automata over a five-letter alphabet. A precise bound in the case of a four-letter alphabet and asymptotic bounds for two- and three-letter alphabets are also provided.