# Given a regular language, calculate its equivalence classes

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.

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.