n-state DFA that requires n-2 steps to check equivalence

Question

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.

Answer 1

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