Help me understand what this Equivalence Relation $≡_L$ is (so I can prove it is one)

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.

• $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$. – Brian Tung Mar 11 at 3:20
• 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. – Brian Tung Mar 11 at 3:22
• 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? – Jay.F Mar 11 at 3:31
• Are you talking about the equivalence relations in the context of the Myhill-Nerode theorem? – ShyPerson Mar 11 at 4:45
• Myhill-Nerode theorem is the theme of the overall assignment – 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.