How do we find all equivalence classes of $\mathsf{R_L}$ for a language?

Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^*011$.

Here's an example they give us in the book http://books.google.com/books?id=VEHYzv0GHt8C&pg=PA73&lpg=PA73&dq=ding+du+example+2.51&source=bl&ots=P8gAls0z7f&sig=HIsMb7rcD3hKZHYzi8fYZsyrLQ8&hl=en&sa=X&ei=5N0nUfSoJ6We2gWOv4HYDQ&ved=0CDMQ6AEwAA

ps The relation $\mathsf{R_L}$ is an equivalent relation. $\mathsf{R_L}$ on $\Sigma^* as:$ $xRy$ iff $(\forall w)[xw \in \mathsf{L} \Leftrightarrow yw \in \mathsf{L}]$

  • $\begingroup$ What is $R_L$? Can you elaborate a little more? $\endgroup$ – Dave Clarke Feb 22 '13 at 20:06
  • $\begingroup$ Equivalent Relation (also added to question) en.wikipedia.org/wiki/Equivalence_relation $\endgroup$ – Iancovici Feb 22 '13 at 20:16
  • 1
    $\begingroup$ Please change the question, rather than just answering in comments. $\endgroup$ – Dave Clarke Feb 22 '13 at 20:42
  • 1
    $\begingroup$ If you take a minimal DFA of some language and try all the possible ways of applying Arden's lemma, you will find a finite number of equivalent regular expressions for that language. That could serve as an algorithm.. and there are finitely many. $\endgroup$ – mrk Feb 22 '13 at 20:59
  • 1
    $\begingroup$ @saadtaame : First, it's a nice solution! As for your example - for a finite language of course there are only finitely many regexes. But for an infinite language there are infinitely many. $\endgroup$ – Shaull Feb 22 '13 at 21:04

You may want to look at Sipser's "Theory of Computation" for a full explanation. Technically, you must first define the problem. What do you mean by "find the equivalence classes"? You probably mean that you want to find a representative of each class, or to find an algorithm that given a word, classifies it to a class.

Probably the easiest way to do so, is to construct a DFA for the language, and then minimize it. By the correctness proof of minimization, the states of the minimal DFA correspond to the equivalence classes.

EDIT: The example in the book doesn't show you how to find the equivalence classes algorithmically. It just shows an example of finding them based on intuition and clever thinking (as you would do with a general mathematical problem). There is no general way to do that.

What the example demonstrates is that if you find these classes, then you can construct a minimal DFA. The interesting point is that the converse is also true.

  • $\begingroup$ Looked at Sipser's but it wasn't as helpful... Were actually using Ding-Zhu Du'sTheory of Computational Complexity $\endgroup$ – Iancovici Feb 22 '13 at 20:21
  • $\begingroup$ None the less, the answer is still valid. You can construct an NFA from the regular expression, determinize it using the subset-construction, and then minimize it using your favorite minimization algorithm (there are several). $\endgroup$ – Shaull Feb 22 '13 at 20:25
  • $\begingroup$ I think you were right about constructing a DFA, that' might've been the step I was missing in the analysis $\endgroup$ – Iancovici Feb 22 '13 at 21:09

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.