It is proved that the set of scattered substrings of a language
recognized by an n-state DFA requires a DFA with at least 2
$^{n/2-2}$
states (the
known upper bound is 2
$^n$
), with witness languages given over an exponentially
growing alphabet. For a 3-letter alphabet, scattered substrings are shown to
require at least 2
$^{sqrt{2n+30}-6}$
states. A similar state complexity
function for scattered superstrings is determined to be exactly 2
$^{n-2}$
+ 1 for an
alphabet of at least n − 2 letters, and strictly less for any smaller alphabet.
For a 3-letter alphabet, the state complexity of scattered superstrings is at
least 1/5 4sqrt{n/2}n-3/4.
