Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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}]$

share|improve this question
    
What is $R_L$? Can you elaborate a little more? –  Dave Clarke Feb 22 '13 at 20:06
    
Equivalent Relation (also added to question) en.wikipedia.org/wiki/Equivalence_relation –  echad Feb 22 '13 at 20:16
1  
Please change the question, rather than just answering in comments. –  Dave Clarke Feb 22 '13 at 20:42
1  
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. –  saadtaame Feb 22 '13 at 20:59
1  
@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. –  Shaull Feb 22 '13 at 21:04
show 14 more comments

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
Looked at Sipser's but it wasn't as helpful... Were actually using Ding-Zhu Du'sTheory of Computational Complexity –  echad Feb 22 '13 at 20:21
    
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). –  Shaull Feb 22 '13 at 20:25
    
I think you were right about constructing a DFA, that' might've been the step I was missing in the analysis –  echad Feb 22 '13 at 21:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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