0
$\begingroup$

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!

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 \}. $$

$\endgroup$

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.