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

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

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

• 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 – Iancovici Feb 22 '13 at 20:16
• Please change the question, rather than just answering in comments. – Dave Clarke Feb 22 '13 at 20:42
• 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
• @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