In theoretical computer science, the separating words problem is the problem of finding the smallest deterministic finite automaton that behaves differently on two given strings, meaning that it accepts one of the two strings and rejects the other string. It is an open problem how large such an automaton must be, in the worst case, as a function of the length of the input strings.
The two strings 0010 and 1000 may be distinguished from each other by a three-state automaton in which the transitions from the start state go to two different states, both of which are terminal in the sense that subsequent transitions from these two states always return to the same state. The state of this automaton records the first symbol of the input string. If one of the two terminal states is accepting and the other is rejecting, then the automaton will accept only one of the strings 0010 and 1000. However, these two strings cannot be distinguished by any automaton with fewer than three states.
For proving bounds on this problem, it may be assumed without loss of generality that the inputs are strings over a two-letter alphabet. For, if two strings over a larger alphabet differ then there exists a string homomorphism that maps them to binary strings of the same length that also differ. Any automaton that distinguishes the binary strings can be translated into an automaton that distinguishes the original strings, without any increase in the number of states.[1]
It may also be assumed that the two strings have equal length. For strings of unequal length, there always exists a prime number whose value is logarithmic in the smaller of the two input lengths, such that the two lengths are different modulo . An automaton that counts the length of its input modulo can be used to distinguish the two strings from each other in this case. Therefore, strings of unequal lengths can always be distinguished from each other by automata with few states.[1]
The problem of bounding the size of an automaton that distinguishes two given strings was first formulated by, who showed that the automaton size is always sublinear.[2] Later, proved the best upper bound known,, on the automaton size that may be required.[3] This was improved by to .[4] [5]
There exist pairs of inputs that are both binary strings of length for which any automaton that distinguishes the inputs must have size . Closing the gap between this lower bound and Chase's upper bound remains an open problem. Jeffrey Shallit has offered a prize of 100 British pounds for any improvement to Robson's upper bound.[6]
Several special cases of the separating words problem are known to be solvable using few states: