2
$\begingroup$

Is it possible for a $DFA$ which has $n$ states that, there exists two distinguishable states $p, q$ such that there exists a distinquishing string between $p$ and $q$ whose length is greater than $n$?

$\endgroup$
2
$\begingroup$

Distinguishing strings can, in general principle, be of any length, though the specifics will depend on the automaton and states that you're looking at.

For example, consider the usual automaton that accepts even-length strings over the alphabet $\{1\}$. We have states $q_\mathrm{e}$ (which is the start state and is accepting) and $q_\mathrm{o}$ (which is not accepting), and the transition function just swaps state every time a character is read. For this automaton, every string over $\{1\}^*$, including the empty string, distinguishes the two states. Strings of even length (including $\epsilon$) distinguish because they're accepted by $q_\mathrm{e}$ and rejected by $q_\mathrm{o}$; odd-length strings are the other way around.

$\endgroup$
1
$\begingroup$

It is a classical fact that if two states are distinguishable, then they are distinguished by a string of length at most $n-1$. This follows from an analysis of Hopcroft's algorithm. See also lecture notes of Luca Trevisan.

Let us say that $q_i \equiv_k q_j$ if $\delta(q_i,w) \in F \Leftrightarrow \delta(q_j,w) \in F$ for all $|w| \leq k$. We can compute $\equiv_k$ inductively as follows:

  • $q_i \equiv_0 q_j$ iff $q_i,q_j \in F$ or $q_i,q_j \notin F$.
  • $q_i \equiv_{k+1} q_j$ iff $q_i \equiv_k q_j$ and for all symbols $\sigma$, $\delta(q_i,\sigma) \equiv_k \delta(q_j,\sigma)$.

If $\equiv_k = \equiv_{k+1}$ then $\equiv_k$ is the Myhill–Nerode relation $\equiv$, since the formula above shows that $\equiv_k = \equiv_m$ for all $m > k$. Conversely, if $\equiv_k \neq \equiv_{k+1}$ then $\equiv_{k+1}$ has more equivalence classes than $\equiv_k$ (since $\equiv_{k+1}$ refines $\equiv_k$). If $\equiv_0 \neq \equiv_1 \neq \cdots \neq \equiv_m$ then $\equiv_m$ must have at least $m$ more equivalence classes than $\equiv_0$, which has at two equivalence classes (in the non-trivial case). Since $\equiv_m$ contains at most $n$ equivalence classes, we deduce that $m \leq n-2$. Hence $\equiv = \equiv_{n-2}$.

$\endgroup$
0
$\begingroup$

Hint: what happens if you remove a loop in the path corresponding to the word?

$\endgroup$
  • $\begingroup$ Yes, it seems impossible the length to be greater than n for this reason, but Hopcroft's algorithm says the upper bound for that length is $\frac{(n-1)(n-2)}{2}-1$. Am I missing something? $\endgroup$ – csinrtoc Mar 18 '18 at 13:51
  • $\begingroup$ @csinrtoc Do you have a reference for that bound? And is it tight? $\endgroup$ – xavierm02 Mar 18 '18 at 13:56
  • $\begingroup$ I have no reference at the moment. I guess I misunderstood some point. Given expression might be related to time complexity of the algorithm, instead of the length of the string. $\endgroup$ – csinrtoc Mar 18 '18 at 14:10
  • $\begingroup$ This hint doesn't seem very useful. Removing a loop from the path starting from state $p$ clearly doesn't change whether the word is accepted from that state, but it might change whether it's accepted from $q$, so the modified string might not be distinguishing. $\endgroup$ – David Richerby Mar 19 '18 at 11:10
  • $\begingroup$ For some reason, I thought csinrtoc wanted to know if the shortest distinguishing word was always of length $\le n$. As DavidRicherby said, removing loops nearly works but not quite. But it suggests looking at loops in $A\times A$ with $(p,q)$ as initial state, and $(p',q')$ final iff exactly one of them is. This gives a $n^2$ bound. If you look more precisely at which states you use, all the states you will use, except the last will be in $(Q\times (Q\setminus F))\cup ((Q\setminus F)\times Q)$ which is of size $\le \frac{n^2}{2}$ which is probably the source the bound csinrtoc provided. $\endgroup$ – xavierm02 Mar 19 '18 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.