I'm kind of new to automata theory and I'm dealing with the equivalence classes used for example in the Myhill-Nerode theorem right now; in other words aba* / a = ba*; aba* / b = ⌀, and such.

In an exercise I'm asked to find a language defined by an infinite set of equivalence classes, but where each class is actually finite. Unfortunately this seems a bit counterintuitive to me, and I can only manage to find languages with an infinite set of equivalence classes where the classes are infinite.

If someone could help me out with the reasoning, and what I'm missing here, I'd really appreciate it.


A random language would do. If $L$ is chosen by putting every word in $\Sigma^*$ in $L$ with probability $1/2$, then for every two given words $x \neq y$ and any third word $z$, the probability that $xz \in L \Leftrightarrow yz \in L$ is $1/2$. Hence almost surely $x$ and $y$ are not equivalent (since we can choose an infinite sequence $z_i$ so that the words $xz_1,yz_1,xz_2,yz_2,\ldots$ are all distinct). Since there are only countably many pairs of words, we find that almost surely, every word is its own equivalence class.

It is also not too difficult to explicitly construct such a language. It suffices to find a subset $A$ of the natural numbers such that for every $x,y \in \mathbb{N}$ there exists $z \in \mathbb{N}$ such that $x+z \in A \not\Leftrightarrow y+z \in A$ (why?). Let $$ A = \bigcup_{i=0}^\infty \{4^i+1,\ldots,2\cdot 4^i\}. $$ Given $x < y$, let $z = 4^y + 1 - y$. Then $z + y = 4^y + 1 \in A$, while $x + z < 4^y + 1$ and $x + z \geq z = 4^y + 1 - y > 2 \cdot 4^{y-1}$ (check!), showing that $x + z \notin A$.


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.