finding separating words (Nerode)

Question

i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me how to do so. also, if you can, would appreciate if you could check if i obtained the correct equivalence classes for both languages.

1)$L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts and ends with} \quad aa\bigg\}$

equivalence classes i've obtained:

$S_1 = \epsilon$

$S_2 = a$

$S_3 = (b+c)\sum^*+a(b+c)\sum^*$

$S_4 = aa+aaa+aa\sum^*aa$

$S_5 = aa\sum^*(b+c)a$

$S_6 = aa\sum^*(b+c)$

2)$L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$

equivalence classes i've obtained:

after joining $\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\}=\{\epsilon, a,b,bba^*\}$ and using the complementary, i've obtained:

$S_1 = \epsilon$

$S_2 = a$

$S_3 = b$

$S_4 = bba*$

$S_5 = c\Sigma^*+a\Sigma^++b(a+c)\Sigma^*+bb\Sigma^*(b+c)\Sigma^*$

how can i find the separating words? also, if you can, could you verify that i've obtained the correct results?

thank you very much!

Answer 1

There are systemic approaches to find the separating words (a.k.a. distinguishers).

However, for small instances of regular languages, I prefer to use plain argument in plain English sometimes. Let me use your case 1) as an example, where you have got all the equivalent classes correctly.

$L$ contains words that start and end with $aa$.
$S_1$ is the empty word.
$S_2$ is the word $a$.
$S_3$ are the words that do not start with $aa$.
$S_4$ are the words that start with $aa$ and end with $aa$.
$S_5$ are the words that start with $aa$ but do not end with $a$.
$S_6$ are the words that start with $aa$ and end with $a$ but not $aa$.

What kind of words can be attached to each group of words to make them in $L$?

$S_1$ + $L$
$S_2$ + words that start with $a$ and end with $aa$.
$S_3$ won't work
$S_4$ + $a$ or words that end with $aa$.
$S_5$ + words that end with $aa$.
$S_6$ + words that end with $a$.

Now that we know these completion groups of words, it is easy to find the separating words.

For example, $S_1$ and $S_2$. We need a word that is in $L$ or that starts with $a$ and ends with $aa$, but not both. The word $abaa$ will do.

For example, $S_5$ and $S_6$. We need a word that ends with $aa$ or that ends with $a$ but not both. The word $a$ will do.