Given a regular language, calculate its equivalence classes

Question

I was given the following regular language:

For any $n$, the language $L_{n}$ consists of all words over $Σ = \{0, 1\}$ whose $n$th character from the end is 1.

I know it's regular because it can be expressed as a regular expression ($\Sigma^{*}1\Sigma^{n-1}$), and I constructed a DFA and an NFA for it. I need to calculate its equivalence classes. I thought that the equivalence classes will be words that have 1 in the same place later in the word - for example one of the classes will be $L(\Sigma^{*}1\Sigma^{n-2})$, because no matter what digit will be added to all these words, the new words will belong to the original language. But I'm not sure I'm on the right track. I would love it if I could understand the process of thinking on this kind of question.

Answer 1

Whether a word and its extensions belongs to $L_n$ or not depends on its final $n$ letters (we'll see later what happens if a word is shorter than $n$ letters). Indeed, we can "probe" all of these letters using the following: for $i=1,\ldots,n$, we have $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. This shows that if two words have different length-$n$ suffixes, then they definitely belong to different equivalence classes.

In contrast, we can check that any two words with the same length-$n$ suffix are equivalent. Indeed, suppose $x,y$ are such words, and consider a word $z$. If $|z| \leq n-1$ then $xz \in L_n$ if the $n-i$'th letter from the end of $x$ is $1$. Since $x,y$ have the same length $n$ suffixes, the condition for $yz \in L_n$ is identical. If $|z| \geq n$, then whether $xz \in L_n$ or not only depends on $z$, and in particular holds just as well for $yz \in L_n$.

Finally, what about words which are shorter than $n$ letters? Recall the test we had above: $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. If $|w| < i$ then $w1^{n-i} \notin L_n$, and so $w$ behaves as if the $i$th letter from the end is $0$. Pursuing this route, we find that the equivalence class of $w$ depends on the length-$n$ suffix of $0^nw$, and this definition works whether $|w| \geq n$ or not.