# Separating words with random DFAs

One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$. I am curious if there any results about the ability of a random DFA to separate two given (nonrandom) strings.

Clearly a random DFA with sufficiently many states separates strings with high probability. Specifically, if $u,v \in \Sigma^n$, a random DFA with $O(n)$ states is unlikely to ever revisit the same state once it reaches the first place where $u$ and $v$ differ, and therefore separates $u$ and $v$.

Can we do better? Ideally, what is the smallest $f(n)$ s.t. that a random DFA with $f(n)$ states separates strings of length $n$ with positive probability (or perhaps probability $\ge 1/2$)? A brief search didn't turn up many results on the properties of random DFAs; all I could find was http://arxiv.org/abs/1311.6830.

• Positive probability isn't a particularly useful condition here, given that it's just a restatement of the open problem. High probability still might be interesting. – Geoffrey Irving May 12 '14 at 16:37
• What does "separates" mean? Accepts one and rejects the other? If so, is it obvious that $O(n)$ states suffices? – usul May 14 '14 at 3:11
• Yes, separates means accepts exactly one. And you're right: the most trivial separation argument actually requires $O(n^2)$ states (what I wrote above is wrong), though I would be surprised if many fewer didn't suffice. – Geoffrey Irving May 14 '14 at 3:23
• Wouldn't you expect the bounds to depend on how much the words differ? It seems like words that differ by a single letter would be harder to discriminate at random, because you need to discriminate at that one transition, and very different words would be easier. [To generalize, you can forget about the longest common prefix (you reach a random state from that); then, differing letters send you either to the same state or to different states; then if the states are different you need to look at the proba of resyncing, and staying in sync (starts depending again on the words)...] – a3nm May 14 '14 at 10:22
• Yes, like the open problem, I am interested in the hardest possible words to discriminate. Words that differ in only a few places can already be separated by $O(\log n)$ states, so they are unlikely to be the hard case. – Geoffrey Irving May 14 '14 at 17:05

This is just an informal idea and I don't know if it helps, but it's too long to be given as a comment. Also, I am not at all familiar with random DFAs, so maybe I have a wrong intuition of how you should reason about probabilities on them, but hopefully this is not entirely worthless.

I will suppose that your bounds should depend on how much $u$ and $v$ differ; if they don't, it seems clear to me that the worst case are strings differing only by their first character (strings differing at a set $X$ of positions have more chances of being told apart than strings differing at a set $Y \subset X$ of positions, I'd say, and putting the difference as early as possible gives you opportunity to resynchronize).

I will also look at the probability that the words are distinguished, namely, they reach different states. I guess you would then need to adapt for being accepted or rejected based on how your random DFAs allocate final states. If each state has a probability 1/2 of being final, then when the strings end up at the same state they are not distinguished, and when they end up at different states they have probability 1/2 of being distinguished.

Now I will consider the word $w$ obtained from $u$ and $v$ as follows: $w_i = 1$ if $u_i = v_i$, and $w_i = 0$ otherwise. I think it is clear that $w$ is the only interesting thing to consider about $u$ and $v$.

Now, define $p(i)$ the probability that we are at the same state after reading prefixes of length $i$ of $u$ and $v$, and $q(i) = 1 - p(i)$ the probability that we aren't.

I think we have $p(i+1) = p(i) + q(i)/n$ when $w_{i+1}$ is $1$. Intuitively, we are at the same state after reading $i+1$ letters either when we were at the same state after reading $i$, or when we were at two different (random) states, we drew two transitions to random states, and they happened to be the same one. Likewise, we have $p(i+1) = 1/n$ when $w_{i+1}$ is $0$: you are drawing two random states, no matter where you started from.

From this I think you could compute the probability of being at the same state after reading $u$ and $v$.

• Unfortunately, it is far from obvious that $w$ is the only interesting property of $u$ and $v$. The easiest way to see this is that there is trivially a nonzero probability of distinguishing any nontrivial $w$ from $0^n$; indeed, only two states suffice regardless of $n$. However, as discussed in arxiv.org/pdf/1103.4513.pdf, there are words $u,v$ of length $n$ s.t. no $o(\log n)$ state DFA can distinguish them. This contradicts your formulas for $p(i)$. – Geoffrey Irving May 14 '14 at 17:12
• To clarify, your formulas would be correct if the DFA transitions were a random function of the string index; since they are independent of index, the probabilities are correlated in a rather complicated fashion. – Geoffrey Irving May 14 '14 at 17:17
• I'm afraid I don't get your counterexample. There is a $>0$ prba, with two states, of distinguishing $0^n$ and $w \neq 0^n$, OK; and maybe there are words of length $n$ that cannot be told apart with $o(\log n)$ states. But how does it contradict my claim that $w$ is the only important thing, or my formulae for $p(i)$? As for correlations, I see there might be a catch of the kind you're mentioning but I don't understand yet why it fails exactly. If you go twice through the same state, there is a correlation, but is there a reason to think it would influence in a certain direction on average? – a3nm May 14 '14 at 21:51
• If $p(n) < 1$, $u$ and $v$ are distinguished with positive probability. However, for sufficiently large $n$ and small numbers of states we know that $p(n) = 1$ for some $u$ and $v$. Since your formulas imply that if $p(i) < 1$ then $p(i+1) = p(i) + (1-p(i))/n = p(i)(1-1/n)+1/n < 1$, your formula is not capturing the fact that certain $u$ and $v$ are impossible to distinguish. – Geoffrey Irving May 15 '14 at 0:19
• Ah... right, I understand. If no small DFA can distinguish two words, then no random DFA can distinguish them either. So indeed there is a problem with my approach, the probability $q(i)$ should drop to zero eventually, because of those correlations, it seems. Sorry for providing an incorrect answer. – a3nm May 15 '14 at 8:00