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

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.

Yuval Filmus · Answer

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 $deltacolon QtimesSigma to Q$.

DFA and equivalence relation

One Answer

Add your own answers!

Ask a Question