# Regular expressions and equivalence classes

I need a little help regarding this problem: Let L = {w ∈ {0, 1} ∗ : w has an even number of 0s and the last character of w is a 1}. Give the equivalence classes of the relation ≡L using regular expressions.

What does it mean with equivalence classes? Is it right that i have found a regular expression for it: 1*(1010)1 --(i think this a right regular expression)

• An equivalence class w.r.t. an equivalence relation $\equiv$ is a maximal (w.r.t. set inclusion) subset $C$ of $L$ such that $x,y \in C$ if and only if $x \equiv y$. We cannot possibly know what the equivalence classes w.r.t. $\equiv_L$ are unless you define $\equiv_L$. Mar 10 at 18:21
• It would be helpful if you help me with an example for this problem so i can continue in my own : Let L = {w ∈ {0, 1} ∗ : w has an even number of 0s and the last character of w is a 1}. Give the equivalence classes of the relation ≡L using regular expressions. Mar 10 at 18:23
• How is $\equiv_L$ defined? Mar 10 at 18:30
• that is all the info i have .I think =L has to be found from the given exercise or am i wrong? Mar 10 at 18:32
• From what I understand you are supposed to know what $\equiv_L$ means already. The equivalence relation $\equiv_L$ partitions $L$ (or perhaps $\Sigma^*$?) into a collection (called quotient set) of equivalence classes. The exercise is asking you to describe these equivalence classes by providing a regular expression for each class. We cannot possibly know what these classes are unless we know what $\equiv_L$ is. Mar 10 at 18:35

I'm going to take a guess and assume that $$\equiv_L$$ is defined as the set of all pairs $$(x,y) \in \Sigma^* \times \Sigma^*$$ such that either (i) $$x \in L$$ and $$y \in L$$, or (ii) $$x \not\in L$$ and $$y \not\in L$$.

In this case $$\Sigma^* / \equiv_L$$ contains two equivalence classes, namely $$L$$ itself and its complement $$\Sigma^* \setminus L$$.

A regular expression for $$L$$ is $$1^*(01^*01^*)^*1$$. Essentially we make sure that $$0$$s always come in pairs and that the last character is a $$1$$.

A regular expression for $$\Sigma^* \setminus L$$ is $$\varepsilon \mid (0\mid1)^*0 \mid 1^*(01^*01^*)^*01^*$$. The first part of the regular expression (i.e., $$\varepsilon$$) matches the empty word. The second part (i.e., $$(0\mid1)^*0$$) matches all words that end with $$0$$, and the third part (i.e., $$1^*(01^*01^*)^*01^*$$) matches all words with an odd number of $$0$$s.

As Nir Shahar points out, another definition of $$\equiv_L$$ could be $$x \equiv_L y$$ if and only if $$\not\exists z \in \mathbb \Sigma^*$$ such that either (i) $$xz \in L$$ and $$yz \not\in L$$ or (ii) $$xz \not\in L$$ and $$yz \in L$$. This is the definition used in the Myhill-Nerode theorem, and word $$z$$ satisfying either (i) or (ii) is called a distinguishing extension for $$x$$ and $$y$$.

In this case $$\Sigma^* / \equiv_L$$ contains the following classes:

• $$C_1$$: The set of all words that have an even number of $$0$$s and end with $$1$$, i.e., $$L$$ itself. A regular expression for $$C_1$$ is given above.
• $$C_2$$: The set of all words that have an odd number of $$0$$s. A regular expression for $$C_2$$ is given above.
• $$C_3$$: The set of all words that have an even number of $$0$$s but do not end with $$1$$. A regular expression for $$C_3$$ is $$(1^* 0 1^* 0)^*$$.

It is easy to see that $$C_1, C_2, C_3$$ partition $$\Sigma^*$$. We just need to show that (A) any two words in $$x,y \in C_i$$ satisfy $$x \equiv_L y$$, and (B) for $$i \neq j$$ there are two words $$x \in C_i$$, $$y \in C_j$$ that do not satisfy $$x \equiv_L y$$.

Regarding (A): If $$z$$ were a distinguishing extensions for either two words in $$x,y \in C_1$$ or two words $$x,y \in C_3$$, then since at least one of $$xz$$ and $$xz$$ must belong to $$L$$ and we must have $$z \neq \varepsilon$$, $$z$$ must end with $$1$$ and must contain an even number of zeroes. However, any such $$z$$ is such that both $$xz \in L$$ and $$xz \in L$$.

If $$z$$ were a distinguishing extensions for two words in $$x,y, \in C_2$$, then since at least one of $$xz$$ and $$xz$$ must belong to $$L$$, $$z$$ must end with $$1$$ and must contain an odd number of zeroes. However, any such $$z$$ is such that both $$xz \in L$$ and $$xz \in L$$.

Regarding (B): $$\varepsilon$$ is a distinguishing extension for $$1 \in C_1$$ and $$0 \in C_2$$. $$1$$ is a distinguishing extension for $$0 \in C_2$$ and $$\varepsilon \in C_3$$. Finally, $$\varepsilon$$ is a distinguishing extension for $$1 \in C_1$$ and $$\varepsilon \in C_3$$.

• My first guess to $\equiv_L$ would actually be something different: $x,y\in \Sigma^*$, and $x\equiv_L y\iff$ there is no distinguishing extension of $x$ and $y$ (that is, the equivalence relation is the Nerode relation over $L$) Mar 11 at 8:24
• @nirshahar. Good point. I expanded my answer. Thank you! Mar 11 at 11:37
• Also, it might be easier to understand if you would write $\forall z, xz\in L\iff yz\in L$ instead of $\not \exists z \dots$. But on the other hand, this definition does not easily define what a "distinguishing extension" is. Mar 11 at 16:05