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.

  • $\begingroup$ I don't understand why it makes any different that $R$ "is related to DFA". The point of mathematics is that it can model many different scenarios at once. An equivalence relation is an equivalence relation whether it comes from the world of set theory, from the world of automata theory, from measure theory, of from any other source. $\endgroup$ – Yuval Filmus Oct 16 '20 at 6:52
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. While Theory of Computation looks a title by Use of Title Case, you might name an author and/or include or hyperlink other information for identification, if not proper credit. $\endgroup$ – greybeard Oct 16 '20 at 9:18

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

  • $\begingroup$ Thanks, but how should I proceed from there? $\endgroup$ – Nimrod Oct 16 '20 at 7:25
  • $\begingroup$ If proving that $R$ is an equivalence relation, you should prove all of these properties. If giving a counterexample, you should design a function $\delta$ which fails to satisfy one of these three conditions. $\endgroup$ – Yuval Filmus Oct 16 '20 at 7:47
  • $\begingroup$ I'm not going to solve this exercise for you, if that's what you're asking. $\endgroup$ – Yuval Filmus Oct 16 '20 at 7:47
  • $\begingroup$ No, that's not it. I'm kind of having trouble understanding all these state transitions $\endgroup$ – Nimrod Oct 16 '20 at 7:53
  • $\begingroup$ What you've answered is merely restating what I've said in the question, that is, the necessary properties R should follow to be an equivalence relation. $\endgroup$ – Nimrod Oct 16 '20 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.