patternMinor
n-state DFA that requires n-2 steps to check equivalence
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.
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\}$:
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$.
- 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.