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.

  • 1
    $\begingroup$ $L_k$ is, in fact, regular. $\endgroup$ – John L. Aug 3 '19 at 18:31
  • $\begingroup$ @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. $\endgroup$ – Limitless Aug 3 '19 at 19:18
  • $\begingroup$ 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? $\endgroup$ – Limitless Aug 3 '19 at 19:19

http://users.utu.fi/jkari/automata/fullnotes.pdf explains equivalence classes well (under section 2.8 "Myhill-Nerode theorem") whence the following notation and definition is borrowed.

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.