DFA and equivalence relation

Question

I was studying Theory of Computation 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

Let me spell what $R$ being an equivalence relation means:

• Reflexivity: for all $q \in Q$ there exists $a \in \Sigma$ such that $\delta(q,a) = \delta(q,a)$.
• Symmetry: for all $q_1,q_2 \in Q$, if there exists $a \in \Sigma$ such that $\delta(q_1,a) = \delta(q_2,a)$ then there exists $b \in \Sigma$ such that $\delta(q_2,b) = \delta(q_1,b)$.
• Transitivity: for all $q_1,q_2,q_3 \in Q$, if there exist $a,b \in \Sigma$ such that $\delta(q_1,a) = \delta(q_2,a)$ and $\delta(q_2,b) = \delta(q_3,b)$ then there exists $c \in \Sigma$ such that $\delta(q_1,c) = \delta(q_3,c)$.

Now it's no longer about DFAs. It's about functions $\delta\colon Q\times\Sigma \to Q$.

Answer 2

To prove R is a equivalance relation then R must be reflexive,symmetric,transitive

1. Reflexive: for all q ∈ Q then there exists a ∈ Σ then δ(q,a)=δ(q,a).
2. Symmetric: for all q1,q2 ∈ Q, if then there exists a ∈ then δ(q1,a)=δ(q2,a) then there exists b∈Σ then δ(q2,b)=δ(q1,b). 3.Transitive: for all q1,q2,q3 ∈ Q, if then there exists a,b ∈ Σ then δ(q1,a)=δ(q2,a) and δ(q2,b)=δ(q3,b) then there exists c ∈ Σ then δ(q1,c)=δ(q3,c). hence R is Equivalance Relation.