The Distinguishability Operation On Regular Languages
Cezar Câmpeanu, Nelma Moreira, Rogério Reis · arXiv (Cornell University) · 2014
In this paper we study the language of the words that, for a given language L, distinguish between pairs of different left-quotients of L. We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators. We give an upper bound for the state complexity of the distinguishability, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different quotients of a language L has at most n - 1 elements, where n is the state complexity of L, and we also study the properties of its iteration.