<p>I believe you have <span class="math-container">$F(n) = n+2$</span> for all <span class="math-container">$n$</span>.</p>
<p>To prove that <span class="math-container">$F(n) \geq n+2$</span>, we prove <span class="math-container">$f(0^n) \geq n+2$</span>: consider any DFA with at most <span class="math-container">$n+1$</span> states, and let <span class="math-container">$q_0,\ldots, q_{n+1}$</span> be the sequence of states visited when reading <span class="math-container">$0^{n+1}$</span>. By the pigeonhole principle, there exist <span class="math-container">$0\leq i&lt;j \leq n+1$</span> such that <span class="math-container">$q_i = q_j$</span>, thus <span class="math-container">$q_i \cdots q_j$</span> is a loop and all the states after <span class="math-container">$q_j$</span> (in particular q_{n+1}) are part of that loop, hence <span class="math-container">$q_{n+1}$</span> is not new.</p>
<p>We have <span class="math-container">$f(z) \leq n+2$</span> for all <span class="math-container">$z \in \{0,1\}^n$</span> as one can build the automaton consisting of a line of <span class="math-container">$n+2$</span> states with a loop on the last one (which I think you already noted, with a slight index mistake).</p>
<p>Therefore <span class="math-container">$F(n) = n+2$</span> for all <span class="math-container">$n$</span></p>

CC BY-SA 4.0
2020-10-14T14:32:31.467Z
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
CC BY-SA 4.0
2020-10-16T12:51:09.793Z
Yes, Emil is exactly correct. Sorry if my question was not more clear!
Zach Hunter
CC BY-SA 4.0
2020-10-14T13:25:40.387Z
2020-10-14T13:25:40.387Z
Corto
<p>The second section of Robson's &quot;Separating strings with small automata&quot; proves <span class="math-container">$F(n) = O((n \log n)^{1/2})$</span>. The string sequence <span class="math-container">$(10^n)^n$</span> gives a lower bound of <span class="math-container">$\Omega(n^{1/2})$</span>. If the automaton has <span class="math-container">$&lt;n$</span> states then both of the sequences <span class="math-container">$\delta_0^{\circ m} (\delta_{(10^n)^{n-1}1}(q_0))$</span> and <span class="math-container">$\delta_{10^n}^{\circ m}(q_0)$</span> will reach a cycle before <span class="math-container">$m=n$</span>.</p>

CC BY-SA 4.0
2020-11-15T18:31:35.297Z
I'm sorry, I'm not familiar with this $\delta$ notation. Could someone give a little explanation for what it is? The example seems correct but I'd love to understand the last sentence.
Zach Hunter
CC BY-SA 4.0
2020-11-15T18:41:08.540Z
@ZacharyHunter $\delta_s$ is the transition function for reading the letter $s$, and we naturally extend it to $\delta_w$ where $w$ is a word. By the $\circ m$ upper index I just meant the composition of such a function with itself $m$ times.
acupoftea
CC BY-SA 4.0
2020-11-15T18:48:12.930Z
thanks, makes sense.
Zach Hunter
CC BY-SA 4.0
2020-11-13T17:46:08.510Z
2020-11-13T18:05:24.680Z
2020-11-13T18:05:24.680Z
acupoftea
<p><strong>Question</strong></p>
<p>Given binary string <span class="math-container">$z \in \{0,1\}^n$</span>, let <span class="math-container">$f(z)$</span> be the smallest integer <span class="math-container">$k$</span> such that there exists a DFA with <span class="math-container">$k$</span> states, such that reading <span class="math-container">$z$</span> from a specific starting state, we end at a state <span class="math-container">$t$</span> where either reading a <span class="math-container">$0$</span> or a <span class="math-container">$1$</span> at <span class="math-container">$t$</span> takes us to a new state. (i.e. a state which has not been reached in the path we took when reading <span class="math-container">$z$</span>)</p>
<p>Then, defining <span class="math-container">$F(n) = \max\{f(z):z \in \{0,1\}^n\}$</span>, I was wondering if any bounds are known for <span class="math-container">$F$</span>. Clearly, we have <span class="math-container">$F(n) \le n+1$</span>.</p>
<p><strong>Motivation</strong></p>
<p>Generally, the <a href="https://en.wikipedia.org/wiki/Separating_words_problem" rel="noreferrer">word separator problem</a> about given distinct binary strings, <span class="math-container">$x,y \in \{0,1\}^n, x \neq y$</span>, to find the smallest DFA such that accepts <span class="math-container">$x$</span> but not <span class="math-container">$y$</span>.</p>
<p>I was wondering if there have been results on this particular method:</p>
<p>Since <span class="math-container">$x\neq y$</span>, let <span class="math-container">$z$</span> be the longest common prefix of <span class="math-container">$x$</span> and <span class="math-container">$y$</span>. (example: if <span class="math-container">$x = 1101101,y=1100110$</span>, then <span class="math-container">$z = 110$</span> because <span class="math-container">$x,y$</span> differ on their fourth letter)</p>
<p>WLOG, lets assume <span class="math-container">$x= z|0|x', y=z|1|y'$</span>, where <span class="math-container">$|$</span> denotes concatenation and <span class="math-container">$x',y'$</span> are arbitrary. If there exists a DFA of length <span class="math-container">$k$</span> such reading <span class="math-container">$z|0$</span> or <span class="math-container">$z|1$</span> ends at a state <span class="math-container">$s'$</span> not visited by reading <span class="math-container">$z$</span>, then there is a DFA of length <span class="math-container">$k +O(\log(n))$</span> separating <span class="math-container">$x$</span> and <span class="math-container">$y$</span>. (because <span class="math-container">$x,y$</span> will reach <span class="math-container">$s'$</span> at different times, it reduces to unary word separation, which is know to take <span class="math-container">$O(\log(n))$</span> states by prime number theorem)</p>
<p><strong>Rough Ideas</strong></p>
<p>Currently this strategy has stuck out to me: we have that <span class="math-container">$f(z) \le g(z_m)+F(n-m)$</span> where <span class="math-container">$z_m$</span> is the subword consisting of the first <span class="math-container">$m$</span> letters in <span class="math-container">$z$</span>, and <span class="math-container">$g(w)$</span> is the smallest integer <span class="math-container">$k$</span> such that there is DFA on <span class="math-container">$k$</span> states, such that reading <span class="math-container">$w$</span> at a specific starting state, we end at a new state <span class="math-container">$t$</span>. For upper bounding <span class="math-container">$g(w)$</span>, for any integers <span class="math-container">$k,i$</span>, and any <span class="math-container">$w' \in \{0,1\}^k$</span>, there exists an DFA on <span class="math-container">$2k$</span> states such that when reading a word <span class="math-container">$w$</span>, we reach the state <span class="math-container">$t$</span> iff <span class="math-container">$w'$</span> appears as a factor/substring whose first letter is the <span class="math-container">$qk+i$</span>-th letter of <span class="math-container">$w$</span>. (i.e. the first letter is the <span class="math-container">$m$</span>-th letter of <span class="math-container">$w$</span> where <span class="math-container">$m$</span> has the same residue as <span class="math-container">$i$</span> modulo <span class="math-container">$k$</span>)</p>
<p>Of course, if <span class="math-container">$z$</span> is a string of only 1's, then <span class="math-container">$g(z_m) = m$</span> for all <span class="math-container">$m$</span>, thus we need to combine this with a second idea to handle the cases when <span class="math-container">$z$</span> is periodic or otherwise not quasi-random in some sense, to get a sublinear bound.</p>

CC BY-SA 4.0
2020-07-30T07:10:50.577Z
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
CC BY-SA 4.0
2020-07-30T07:12:40.250Z
What do you mean by "$x, y$ will reach $s'$ at different times"?
J.-E. Pin
CC BY-SA 4.0
2020-07-30T20:05:16.567Z
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'$.
Zach Hunter
CC BY-SA 4.0
2020-07-30T20:21:43.853Z
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
CC BY-SA 4.0
2020-07-30T20:29:18.423Z
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.
Zach Hunter
CC BY-SA 4.0
2020-10-16T13:38:10.180Z
Is it the case that $f(z) = \min(g(z0), g(z1))$?  And $g(z) \le f(z)+1$?  Just checking that I understand the definitions.
Neal Young
CC BY-SA 4.0
2020-10-17T00:03:49.177Z
The first statement is true, the second could be false. For example, if $z = 1111$, then $g(z) = 5$ yet $f(z) = 2$.

However, I am hoping to prove that when the values of $g(z_m)$ grow at sufficiently fast rate, that $z$ must have some type of structure which we can use to otherwise bound $f(z)$.
Zach Hunter
<automata-theory><dfa>
Bounds on this Strategy for Separating Words
Zach Hunter
# Bounds on this Strategy for Separating Words

(Asked by: username_0 on 2020-07-28)

**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](https://en.wikipedia.org/wiki/Separating_words_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.

**Tags:** automata-theory, dfa

> **Comments:**
> **username_1**: 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$?  
> **username_1**: What do you mean by "$x, y$ will reach $s'$ at different times"?  
> **username_0**: 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'$.  
> **username_2**: 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?  
> **username_0**: 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.  
> **username_3**: Is it the case that $f(z) = \min(g(z0), g(z1))$?  And $g(z) \le f(z)+1$?  Just checking that I understand the definitions.  
> **username_0**: The first statement is true, the second could be false. For example, if $z = 1111$, then $g(z) = 5$ yet $f(z) = 2$.  However, I am hoping to prove that when the values of $g(z_m)$ grow at sufficiently fast rate, that $z$ must have some type of structure which we can use to otherwise bound $f(z)$.  

---

## 2 answers

### Answer by username_6 on 2020-11-13. Score: 6 | Accepted answer

The second section of Robson's "Separating strings with small automata" proves $F(n) = O((n \log n)^{1/2})$. The string sequence $(10^n)^n$ gives a lower bound of $\Omega(n^{1/2})$. If the automaton has $ states then both of the sequences $\delta\_0^{\circ m} (\delta\_{(10^n)^{n-1}1}(q\_0))$ and $\delta\_{10^n}^{\circ m}(q\_0)$ will reach a cycle before $m=n$.

> **Comments:**
> **username_0**: I'm sorry, I'm not familiar with this $\delta$ notation. Could someone give a little explanation for what it is? The example seems correct but I'd love to understand the last sentence.  
> **username_6**: @ZacharyHunter $\delta_s$ is the transition function for reading the letter $s$, and we naturally extend it to $\delta_w$ where $w$ is a word. By the $\circ m$ upper index I just meant the composition of such a function with itself $m$ times.  
> **username_0**: thanks, makes sense.  

---

### Answer by username_4 on 2020-10-14. Score: 0

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$

> **Comments:**
> **username_5**: 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.  
> **username_0**: Yes, Emil is exactly correct. Sorry if my question was not more clear!  

---

