Computer Science Asked by Nimrod on December 14, 2020

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.

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

Answered by Yuval Filmus on December 14, 2020

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP