Finding Nerode equivalence classes of non regular languages

Question

I am trying to understand how to find equivalence classes for this non-regular language but I cannot really understand it. $$ L= \{ c^nw \mid n \in \mathbb{N}\space \text{and}\space w \in \{ a, b \}^* \space \text{and}\space |w| = n \} $$ Can someone guide on what to think or consider to solve this? What is the best approach to determine the equivalence classes of a non-regular language, e.g. for the language above? How would you proceed?

Answer 1

Let $\Sigma$ be a finite alphabet and let $L \subseteq \Sigma^*$ be a language. In our case, $\Sigma = \{a,b,c\}$ and

$$ L = \{ c^nw \mid n \in \mathbb{N} \wedge w \in \{a,b\}^* \wedge |w|=n\} \enspace. $$

Two words $u$ and $v$ in $\Sigma^*$ are equivalent w.r.t. $L$ if, for all words $z \in \Sigma^*$, $uz \in L$ if and only if $vz \in L$. Said otherwise, two words are equivalent if adding the same suffix to both results in two words that are either both in $L$ or both not in $L$.

A finite automaton accepts an infinite language, one containing infinitely many words, precisely when $\Sigma^*$ is divided into finitely many equivalence classes. Each class then corresponds to one state of the minimal DFA accepting $L$.

---

For our $L$, words that don't have all their $c$'s before the $a$'s and $b$'s are irrecoverable: there is no way to extend a word like $cac$ to a word in $L$. All these words are in the same equivalence class, which contains also irrecoverable words like $ccaaa$.

A word that contains no $a$ or $b$ (it is $c^n$ for some $n$) cannot be in the same class as any other word. (Can you find an extension that proves it?)

For words of the form $c^nu$, with $u \in \{a,b\}^m$ and $1 \leq m \leq n$, what matters is $n-m$; hence each nonnegative value of $n-m$ gives a different equivalence class. (How would you describe the class corresponding to $m=n$?)

Clearly our $L$ is not regular because there is no upper bound on $n$.