# Myhill-Nerode equivalence classes

I need to find the Myhill-Nerode equivalence classes for the language $$L = \Sigma^*\setminus \left( \{\epsilon, cc \} \cup \{ cca^i: i\geq 2 \} \right)$$ over $$\Sigma = \{a, b, c \}$$

I'm familiar with the idea of separating suffix, but I really don't know where to start here. Thanks!

To begin with, note the the Myhill-Nerode equivalence classes for a language $$L$$ is the same as the Myhill-Nerode classes for its complement $$\overline{L}$$. This follows immediately by definition, and I leave it you (it also appears here).

So given $$\Sigma = \{a, b, c\}$$, we need to find the Myhill-Nerode classes for $$\overline{L} = \{ \epsilon, cc\}\cup \{cca^i: i\geq 2 \}$$. There are many ways to do so, one can, for example, consider what happens in a minimal deterministic automaton for the language - it is known that the states of the minimal deterministic automaton correspond to the Myhill-Nerode classes. Yet, the given language is simple enough, you can actually experiment with it a bit and show that the following are the equivalence class for $$\overline{L}$$ (indeed, $$\overline{L}$$ has a simple structure - every word of length at least $$4$$ in the laguage is of the form $$cca^i$$, so clearly all these words are equivalent. Then, you can look at words of length < 4, and try to see which among them are equivalent, etc.):

• $$C_1 = \{ \epsilon\}$$.
• $$C_2 = \{ c\}$$.
• $$C_3 = \{ cc\}$$.
• $$C_4 = \{ cca\}$$.
• $$C_5 = \{ cca^i: i\geq 2\}$$.
• $$C_6 = \Sigma^*\setminus \left( \bigcup_{i\in [5]} C_i\right)$$.

Clearly the 5 sets above partition $$\Sigma^*$$, so to show that they are indeed the Myhill-Nerode classes, we need to show that all the words in the same set are Myhill-Nerode equivalent, and for every $$1\leq i < j \leq 6$$, it holds that the words in the set $$C_i$$ are not equivalent to the words in the set $$C_j$$.

There you go, try to prove that the above sets are indeed the equivalence classes. That should be easy enough now.

The equivalence classes for $$L$$ are the same as those for $$\overline{L} = \{cca^i \, : \, i \ge 2\} \cup \{\varepsilon, cc\}$$.

All the words in $$\{cca^i \, : \, i \ge 2\}$$ belong to the same equivalence class $$C_1$$. Indeed let $$\alpha, \beta \in \{cca^i \, : \, i \ge 2\}$$ and consider any extension $$x$$, if $$x \neq a^k$$ for some $$k$$, then neither $$\alpha x$$ nor $$\beta x$$ belong to $$\overline{L}$$. Otherwise they both belong to $$\overline{L}$$.

The word $$cc$$ belongs to some equivalence class $$C_2 \neq C_1$$. Indeed $$a$$ is a distinguishing extension for $$cc$$ and $$ccaa \in C_1$$.

The word $$\varepsilon$$ belongs to some equivalence class $$C_3 \not\in \{C_1, C_2\}$$. Indeed (i) $$cc$$ is a distinguishing extension for $$\varepsilon$$ and $$cc \in C_2$$, and (ii) $$a$$ is a distinguishing extension for $$\varepsilon$$ and $$ccaa \in C_1$$.

The word $$c$$ belongs to some equivalence class $$C_4 \not\in \{C_1, C_2, C_3\}$$. Indeed $$\varepsilon$$ is a distinguishing extension for $$c$$ and any word in $$C_1$$, $$C_2$$, or $$C_3$$.

The word $$cca$$ belongs to some equivalence class $$C_5 \not\in \{C_1, C_2, C_3, C_4\}$$. Indeed (i) $$\varepsilon$$ is a distinguishing extension for $$cca$$ and any word in $$C_1$$, $$C_2$$, or $$C_3$$, and (ii) $$a$$ is a distinguishing extension for $$cca$$ and $$c \in C_4$$.

All other words $$\gamma$$ do not start with any prefix of $$cca^*$$. Therefore there exist no extension $$x$$ such that $$\gamma x \in \overline{L}$$. Moreover (i) $$\varepsilon$$ is a distinguishing extension for $$\gamma$$ and any word in $$C_1$$, $$C_2$$, or $$C_3$$, and there exists at least one distinguishing extension for $$c \in C_4$$ (namely $$c$$), and for $$cca \in C_5$$ (namely $$a$$). This shows that all these words $$\gamma$$ belong to the same equivalence class.

The equivalence classes are then: $$\{cca^i \, : \, i \ge 2\}, \; \{cc\}, \; \{ \varepsilon\}, \; \{ c\}, \; \{ cca \}, \Sigma^* \setminus \{cca^k \, : \, k \ge 0 \}.$$