# Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$

I want to formally write the equivalence classes of the following language: $$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$

I understand the definition of equivalence classes, yet struggle to come up with a clear intuitive answer.

The language is regular, therefore i'd expect finite equivalence classes.

It seems like the essence of the information I am looking for is only "what is the $$k$$-th bit from the right", which means i want to focus my attention on suffixes in the form of $$\sigma y \in \{0,1\}^*$$ where $$|y|=k-1$$, $$\sigma\in \Sigma$$.

I would highly appreciate some guidance that would build my intuition for finding equivalence classes in general, and in this specific case.

• $L_k$ is, in fact, regular. – Apass.Jack Aug 3 at 18:31
• @Apass.Jack You are correct, for a moment i confused the question for arbitrary k and that caused me some serious trouble. I've edited the question, but still I lack understanding of how to find equivalence classes in such cases. – Limitless Aug 3 at 19:18
• I understand that for a suffix Z where |Z|>K-1, any two prefixes are equivalent, but how do I handle the case where |Z|<K? – Limitless Aug 3 at 19:19

Define $$\text{Ext}(w,L) =\{x\mid wx\in L\}$$ where $$w$$ is in $$\Sigma^*$$ and $$L$$ is the language, ie. the set contains of all suffixes that, when added to $$w$$, yields a word in $$L$$.
Two words $$a$$ and $$b$$ are in the same equivalence class if $$\text{Ext}(a,L)=\text{Ext}(b,L)$$.
For the language $$L_k$$ described, only the last $$k$$ letters of $$w$$ matter when figuring out $$\text{Ext}(w,L_k)$$ for any word $$w$$ because the other letters do not matter as they do not contribute to the condition "the $$k$$-th bit of $$w$$ from the right is $$1$$". Since there are only finitely many combinations for the last $$k$$ letters, specifically $$2^k$$, there are a finite number of equivalence classes in $$L_k$$.
As per your edit about suffixes of length less than $$k$$, sure, $$\text{Ext}$$ can contain such suffixes, but they do not matter in showing that there exist finitely many equivalence classes.