DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$

Problem Detail: 

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

Asked By : Iancovici

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10029