18

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.

Community
  • 1
Geoffrey Irving
  • 3,253
  • 15
  • 29
  • 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
  • 1
    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 03: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 03:23
  • 1
    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
  • Here is another result on random DFAs, with more references therein https://www.sciencedirect.com/science/article/pii/S0304397516304881 – Aryeh Jun 24 '21 at 06:17

2 Answers2

6

It appears, via code, that if you take a random string $x$ and then form $y$ by flipping only the first bit of $x$, then a random DFA on $n/5$ states fails to separate $x,y$ with high probability. So, in particular, there exists a pair $x,y$ such that a random DFA on $n/5$ states fails to separate $x,y$ with high probability.

mathworker21
  • 321
  • 1
  • 3
  • 7
1

[Edit: this answer does not work, see comments.]

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$.

a3nm
  • 9,269
  • 27
  • 86
  • 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 http://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
  • 1
    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 00: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 08:00