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$
  • 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$ – Yuval Filmus Mar 12 '17 at 14:46
  • $\begingroup$ Try the language $\{ x \in 0^* : |x| < n \}$. $\endgroup$ – Yuval Filmus Mar 12 '17 at 17:12
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, privacy policy and cookie policy

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