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.
Best Answer
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.