Discerning Two Words by a Minimum Size Automaton
J. (Jiří) Wiedermann · Digital Repository (National Repository of Grey Literature) · 2016
In 1986 Goralčík and Koubek proved that there is a DFA of sublinear size distinguishing between two words of length ≤ n (by accepting one and rejecting the other).In 1989 Robson designed a DFA of size O(n 2/5 (log n) 3/5 ) representing the best known upper bound for this problem until today.Improving this bound has been formulated as an open problem in automata theory by several authors.In this paper we definitely resolve this problem by showing a DFA of size O(log n) which is asymptotically optimal.We also characterize the class of regular languages recognized by the underlying automata.