1
$\begingroup$

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)

$\endgroup$
6
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Steven
    Mar 10 at 18:21
  • $\begingroup$ 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. $\endgroup$
    – yaman
    Mar 10 at 18:23
  • $\begingroup$ How is $\equiv_L$ defined? $\endgroup$
    – Steven
    Mar 10 at 18:30
  • $\begingroup$ that is all the info i have .I think =L has to be found from the given exercise or am i wrong? $\endgroup$
    – yaman
    Mar 10 at 18:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Mar 10 at 18:35

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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$) $\endgroup$
    – nir shahar
    Mar 11 at 8:24
  • $\begingroup$ @nirshahar. Good point. I expanded my answer. Thank you! $\endgroup$
    – Steven
    Mar 11 at 11:37
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Mar 11 at 16:05

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.