HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dfarequiresthatstatecheckstepsequivalence

Problem

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.

Solution

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



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

Context

StackExchange Computer Science Q#71428, answer score: 2

Revisions (0)

No revisions yet.