4
$\begingroup$

We have a DFA $A = (Q,\Sigma, \delta, q_0, F)$. States $p, q$ $\in Q$ are equivalent, $p \sim q$ if $ \forall w \in \Sigma ^ \ast$ $ \delta^*(p,w) \in F \iff \delta^*(q,w) \in F$

States $p,q$ are equivalent after $i$ steps, $p \sim ^i q$, if $ \forall w \in \Sigma ^ \ast$ such that $|w|\le i$ $ \delta^*(p,w) \in F \iff \delta^*(q,w) \in F$

$p \sim q$, if $ \forall i$ $p \sim ^i q$

State equivalence $\sim$ creates a partition $Q/\sim$ of states to equivalence classes.

I am trying to find a $n$-state DFA for all $n \ge 2$ where the state equivalence relation $\sim$ is equal to the state equivalence relation after $n - 2$ steps, $\sim^{n-2}$, but is not equal to the state equivalence relation after $n - 3$ steps, $\sim^{n-3}$.

So I'm searching for DFAs which require exactly $n - 2$ transitions to check the equivalence. I don't know how to approach this problem.

$\endgroup$
2
  • 1
    $\begingroup$ In any case, I would suggest solving this for $n=3,4,5,\ldots$, and then trying to find a solution for general $n$. $\endgroup$ Mar 12, 2017 at 14:46
  • $\begingroup$ Try the language $\{ x \in 0^* : |x| < n \}$. $\endgroup$ Mar 12, 2017 at 17:12

1 Answer 1

2
$\begingroup$

Consider the following DFA on the alphabet $\{0\}$:

  • The states are $q_1,\ldots,q_n$, with $q_1$ initial and $q_n$ final.
  • $\delta(q_i,0) = q_{i+1}$ for $i < n$, and $\delta(q_n,0) = q_n$.

Consider the pair of states $q_1,q_2$. For $i < n-2$, $\delta^*(q_1,0^i),\delta^*(q_2,0^i) \notin F$, whereas $\delta^*(q_1,0^{n-2}) = q_{n-1} \notin F$, $\delta^*(q_2,0^{n-2}) = q_n \in F$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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