View source for Separating words problem

In [[theoretical computer science]], the '''separating words problem''' is the problem of finding the smallest [[deterministic finite automaton]] that behaves differently on two given [[String (computer science)|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.

== See also ==

* [[Deterministic finite automaton]]
* [[String (computer science)]]

== External links ==

* [https://en.wikipedia.org/wiki/Separating_words_problem Separating words problem] @ Wikipedia

[[Category:Computer science]]
[[Category:Computing]]