Equivalence relations and State transitions

Question

I was studying automata theory and I'm kind of lost in solving this problem.

Let $R$ be a relation defined on the set of states $Q$ of a DFA as $q_1Rq_2$ if $\delta(q_1,a)=\delta(q_2,a)$ for some $a\in\Sigma$.

Is $R$ an equivalence relation? Prove.

So to prove that $R$ is an equivalence relation, I have to show that

• $R$ is reflexive
• $R$ is symmetric
• $R$ is transitive

But since it's related to DFA, I'm not sure how to approach this problem. Some help is much appreciated.

Answer 1

Clearly, the relation $R$ is reflexive and symmetric.
To see that it is not transitive, consider the three-state automaton on the picture given in this section of the Wikipedia page.

Here, we have $\delta(q_0,1) = q_0 = \delta(q_1,1)$, so that $q_0 R q_1$;
also $\delta(q_1,0) = q_2 = \delta(q_2,0)$, whence $q_1 R q_2$.
Nevertheless, there is no $x$ such that $\delta(q_0,x) = \delta(q_2,x)$; this is because $\delta(q_2,x)=q_2$, for all $x$, and $\delta(q_0,x) \in \{q_0,q_1\}$.
Hence $(q_0,q_2) \notin R$ and so $R$ is not transitive.