# finding separating words (Nerode)

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!

• "I have found the equivalence classes." How did you find them? The equivalence classes are usually defined by the separating words. Since you have found the equivalence classes, you are supposed to have found the separating words. – John L. Dec 25 '18 at 22:10
• well what you said is not true. i'll explain to you what i did - i found a regular expression that represents each equivalence class(partition) i found. after that, we usually put the data in some sort of a table where it's s1...sn and sn...s1(one in the horizontal and one in the vertical), and then you find the separating words. however, i don't understand this method and that's what i asked, an explanation on how to do it correctly. – cse111 Dec 26 '18 at 13:31

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.