# Bounds on this Strategy for Separating Words

Question

Given binary string $$z \in \{0,1\}^n$$, let $$f(z)$$ be the smallest integer $$k$$ such that there exists a DFA with $$k$$ states, such that reading $$z$$ from a specific starting state, we end at a state $$t$$ where either reading a $$0$$ or a $$1$$ at $$t$$ takes us to a new state. (i.e. a state which has not been reached in the path we took when reading $$z$$)

Then, defining $$F(n) = \max\{f(z):z \in \{0,1\}^n\}$$, I was wondering if any bounds are known for $$F$$. Clearly, we have $$F(n) \le n+1$$.

Motivation

Generally, the word separator problem about given distinct binary strings, $$x,y \in \{0,1\}^n, x \neq y$$, to find the smallest DFA such that accepts $$x$$ but not $$y$$.

I was wondering if there have been results on this particular method:

Since $$x\neq y$$, let $$z$$ be the longest common prefix of $$x$$ and $$y$$. (example: if $$x = 1101101,y=1100110$$, then $$z = 110$$ because $$x,y$$ differ on their fourth letter)

WLOG, lets assume $$x= z|0|x', y=z|1|y'$$, where $$|$$ denotes concatenation and $$x',y'$$ are arbitrary. If there exists a DFA of length $$k$$ such reading $$z|0$$ or $$z|1$$ ends at a state $$s'$$ not visited by reading $$z$$, then there is a DFA of length $$k +O(\log(n))$$ separating $$x$$ and $$y$$. (because $$x,y$$ will reach $$s'$$ at different times, it reduces to unary word separation, which is know to take $$O(\log(n))$$ states by prime number theorem)

Rough Ideas

Currently this strategy has stuck out to me: we have that $$f(z) \le g(z_m)+F(n-m)$$ where $$z_m$$ is the subword consisting of the first $$m$$ letters in $$z$$, and $$g(w)$$ is the smallest integer $$k$$ such that there is DFA on $$k$$ states, such that reading $$w$$ at a specific starting state, we end at a new state $$t$$. For upper bounding $$g(w)$$, for any integers $$k,i$$, and any $$w' \in \{0,1\}^k$$, there exists an DFA on $$2k$$ states such that when reading a word $$w$$, we reach the state $$t$$ iff $$w'$$ appears as a factor/substring whose first letter is the $$qk+i$$-th letter of $$w$$. (i.e. the first letter is the $$m$$-th letter of $$w$$ where $$m$$ has the same residue as $$i$$ modulo $$k$$)

Of course, if $$z$$ is a string of only 1's, then $$g(z_m) = m$$ for all $$m$$, thus we need to combine this with a second idea to handle the cases when $$z$$ is periodic or otherwise not quasi-random in some sense, to get a sublinear bound.

• What do you mean precisely by "takes us to a new state"? Do you mean that this new state $s$ is different from $t$, or that the path $i \xrightarrow{z} t$ does not visit $s$? – J.-E. Pin Jul 30 at 7:10
• What do you mean by "$x, y$ will reach $s'$ at different times"? – J.-E. Pin Jul 30 at 7:12
• by new state I meant that the path $i \to t$ did not visit $s$. by $x,y$ will reach $s'$ at different times, I mean that we need to read more letters of $x,y$ before we can possibly reach $s'$. thus, we can append a unary DFA that can only be reached through $s'$ and cannot be exited, which differentiates $x,y$ since they have different number of letters left once they finally reach $s'$. – Zachary Hunter Jul 30 at 20:05
• I don't understand the second clarification. If both $z0$ and $z1$ lead to $s'$, doesn't that mean that both $x$ and $y$ drive the DFA to $s'$ after exactly $|z|+1$ steps? – Radu GRIGore Jul 30 at 20:21
• I find it useful to think that I'm constructing the DFA on the go, only determine 0 edges and 1 edges when I need to. if $z|0$ takes us to $s'$, which has never been reached before, then there exists we can have $z|1$ not lead to $s'$. (if the 1 edge at that state has already been used previously, then obviously it does not lead to $s'$, as it has never been reached, otherwise, the 1 edge is also undetermined, so we may choose to have it not lead to $s'$) alternatively we could say that the DFA may be modified such that $x$ and $y$ are driven to $s'$ after a different number of steps. – Zachary Hunter Jul 30 at 20:29

I believe you have $$F(n) = n+2$$ for all $$n$$.
To prove that $$F(n) \geq n+2$$, we prove $$f(0^n) \geq n+2$$: consider any DFA with at most $$n+1$$ states, and let $$q_0,\ldots, q_{n+1}$$ be the sequence of states visited when reading $$0^{n+1}$$. By the pigeonhole principle, there exist $$0\leq i such that $$q_i = q_j$$, thus $$q_i \cdots q_j$$ is a loop and all the states after $$q_j$$ (in particular q_{n+1}) are part of that loop, hence $$q_{n+1}$$ is not new.
We have $$f(z) \leq n+2$$ for all $$z \in \{0,1\}^n$$ as one can build the automaton consisting of a line of $$n+2$$ states with a loop on the last one (which I think you already noted, with a slight index mistake).
Therefore $$F(n) = n+2$$ for all $$n$$
• The condition is that reading $z|0$ or reading $z|1$ will lead to a new state, not that both of them do. Thus, $f(0^n)=2$: it suffices to take the 2-state automaton that has a $0$-loop on the starting state, and a $1$-transition to the other state. – Emil Jeřábek Oct 14 at 14:32