I'm trying to answer the following exercise question:

Exercise 1. Let $Σ =\{0, 1\}$ and let $L$ be a set of strings. As seen in lectures, $L$ induces an equivalence relation denoted $≡_L$ over the set of strings. Prove $≡_L$ is an equivalence relation, i.e. it satisfies the 3 properties (symmetry, reflexivity and transitivity).

As I understand it there is no equivalence relation described in the question. An equivalence relation would be something like "$a$ is related to $b$ (i.e $a ≡_L b$) if $a-b$ is an integer".

So here is my attempt at transcribing the relevant lecture notes:

$L$ is a set
$L-x=\{y : xy ∈ L\}$
$x ≡_L y \iff L-x = L-y$

I am unclear what is being described here. "$L$ is a set" - ok, in this $L$ could be say $\{0, 01, 0101\}$ or similar. The following lines describe what the relation actually is but I can't understand them. Can anyone please help me so I can go about proving the transitivity/reflexivity/symmetry of the equivalence to answer the question.

Is it saying the set $L-x=y$, such that $xy$ is an element of the set $L$? That doesn't seem intuitive.

  • $\begingroup$ $L$ is a set of strings, and for any single string $x$, $L-x$ denotes the set of suffixes for which $x$ is a prefix. That is to say, given $x$, collect all the strings in $L$ that start with $x$. The set of strings that you get when you remove the initial $x$ in that collection—that's what $L-x$ is. For instance, if $L$ is, say, all strings of length $6$ that have an even number of $1$s in them, then $L-001 = \{001, 010, 100, 111\}$, because the set of strings in $L$ that begin with $001$ is $\{001001, 001010, 001100, 001111\}$. Remove the initial $001$ from each, and you get $L-001$. $\endgroup$ – Brian Tung Mar 11 at 3:20
  • $\begingroup$ You have to show, presumably, that the relation $x \sim_L y \Leftrightarrow L-x = L-y$ is in fact an equivalence relation, whatever $L$ happens to be. If you think about what this relation is, this shouldn't be too difficult, I don't think. $\endgroup$ – Brian Tung Mar 11 at 3:22
  • $\begingroup$ Thank you that seems right on the money, the question makes sense now. So ≡L is basically "the prefix and suffix are the same" ex {010010, 101101}? p.s I can't seem to upvote or select as the correct answer (Im normally on stackoverflow and cs.stackexchange) I assume the community will do this? $\endgroup$ – Jay.F Mar 11 at 3:31
  • $\begingroup$ Are you talking about the equivalence relations in the context of the Myhill-Nerode theorem? $\endgroup$ – ShyPerson Mar 11 at 4:45
  • $\begingroup$ Myhill-Nerode theorem is the theme of the overall assignment $\endgroup$ – Jay.F Mar 11 at 4:56

The wording of the exercise could easily have been made more precise. I suppose that $L$ is a set of strings in $\Sigma,$ that is, $L \subseteq \Sigma,$ and that when we say $L$ "induces an equivalence relation ... over the set of strings," we really mean an equivalence relation over $\Sigma.$

If $L$ is a set of strings and $x$ is a string, then the definition from the lecture says that $L - x$ also is a set of strings, specifically all the strings that you can append to $x$ in order to get a string in $L.$

You could think of it this way: a string $y$ is a "good" suffix of $x$ if you can append $y$ to $x$ and get a string in $L,$ that is, $xy\in L.$ Then $L - x$ as the set of "good" suffixes of $x.$ Note that if $x$ itself is in $L,$ then one of the "good" suffixes is the empty string.

The relationship according to your notes is that $x \equiv_L y$ iff the "good" suffixes of $x$ are exactly the same as the "good" suffixes of $y.$

If $L = \{0, 01, 0101\},$ as in your example, then $L - 010 = \{1\},$ $L - 01 = \{e, 01\}$ (where $e$ is the empty string), and $L - 0 = \{e, 1, 101\}.$ But $L - 1 = \emptyset$; if you start a string with $1,$ there is no way to finish the string in order to make it something in $L.$ On the other hand, $L - e = L.$ (Actually that last fact would be true no matter what you chose for the members of $L.$)

So $01 \not\equiv_L 010$ in your example, because $\{e, 01\} \neq \{1\}.$ Likewise $0 \not\equiv_L 01.$ But $1 \equiv_L 11,$ because $L - 1 = L - 11 = \emptyset.$ In fact if you choose any $x$ and $y$ that are not prefixes of any string in $L$ then $L - x = L - y = \emptyset$ and therefore $x \equiv_L y.$

As for proving the equivalence relation, it's a relatively mechanical task. You need to show that if $x, y, z \in \Sigma,$ then $x\equiv_L y$ implies $y\equiv_L x$ (symmetry), $x\equiv_L x$ (reflexivity), and if $x\equiv_L y$ and $y\equiv_L z$ then $x\equiv_L z$ (transitivity). For example, for symmetry, if the set of "good" suffixes of $x$ is the same as the set of "good" suffixes of $y,$ is it always true that the set of "good" suffixes of $y$ is the same as the set of "good" suffixes of $x$? The trick is to write this formally, using the symbology from your notes.


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.