finding separating words (Nerode) - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T13:40:42Z https://cs.stackexchange.com/feeds/question/102039 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/102039 2 finding separating words (Nerode) cse111 https://cs.stackexchange.com/users/98234 2018-12-25T17:44:05Z 2019-01-26T14:01:55Z <p>i have found the equivalence classes of given <span class="math-container">$R_L$</span> 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.</p> <p>1)<span class="math-container">$L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts and ends with} \quad aa\bigg\}$</span></p> <p>equivalence classes i've obtained:</p> <p><span class="math-container">$S_1 = \epsilon$</span></p> <p><span class="math-container">$S_2 = a$</span></p> <p><span class="math-container">$S_3 = (b+c)\sum^*+a(b+c)\sum^*$</span></p> <p><span class="math-container">$S_4 = aa+aaa+aa\sum^*aa$</span></p> <p><span class="math-container">$S_5 = aa\sum^*(b+c)a$</span> </p> <p><span class="math-container">$S_6 = aa\sum^*(b+c)$</span></p> <p>2)<span class="math-container">$L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$</span></p> <p>equivalence classes i've obtained:</p> <p>after joining <span class="math-container">$\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\}=\{\epsilon, a,b,bba^*\}$</span> and using the complementary, i've obtained:</p> <p><span class="math-container">$S_1 = \epsilon$</span></p> <p><span class="math-container">$S_2 = a$</span></p> <p><span class="math-container">$S_3 = b$</span></p> <p><span class="math-container">$S_4 = bba*$</span></p> <p><span class="math-container">$S_5 = c\Sigma^*+a\Sigma^++b(a+c)\Sigma^*+bb\Sigma^*(b+c)\Sigma^*$</span></p> <p>how can i find the separating words? also, if you can, could you verify that i've obtained the correct results?</p> <p>thank you very much!</p> https://cs.stackexchange.com/questions/102039/-/102091#102091 2 Answer by Apass.Jack for finding separating words (Nerode) Apass.Jack https://cs.stackexchange.com/users/91753 2018-12-27T13:17:50Z 2018-12-27T13:17:50Z <p>There are systemic approaches to find the separating words (a.k.a. distinguishers).</p> <p>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.</p> <p><span class="math-container">$L$</span> contains words that start and end with <span class="math-container">$aa$</span>.<br> <span class="math-container">$S_1$</span> is the empty word.<br> <span class="math-container">$S_2$</span> is the word <span class="math-container">$a$</span>.<br> <span class="math-container">$S_3$</span> are the words that do not start with <span class="math-container">$aa$</span>.<br> <span class="math-container">$S_4$</span> are the words that start with <span class="math-container">$aa$</span> and end with <span class="math-container">$aa$</span>.<br> <span class="math-container">$S_5$</span> are the words that start with <span class="math-container">$aa$</span> but do not end with <span class="math-container">$a$</span>.<br> <span class="math-container">$S_6$</span> are the words that start with <span class="math-container">$aa$</span> and end with <span class="math-container">$a$</span> but not <span class="math-container">$aa$</span>.</p> <p>What kind of words can be attached to each group of words to make them in <span class="math-container">$L$</span>?</p> <p><span class="math-container">$S_1$</span> + <span class="math-container">$L$</span><br> <span class="math-container">$S_2$</span> + words that start with <span class="math-container">$a$</span> and end with <span class="math-container">$aa$</span>.<br> <span class="math-container">$S_3$</span> won't work<br> <span class="math-container">$S_4$</span> + <span class="math-container">$a$</span> or words that end with <span class="math-container">$aa$</span>.<br> <span class="math-container">$S_5$</span> + words that end with <span class="math-container">$aa$</span>.<br> <span class="math-container">$S_6$</span> + words that end with <span class="math-container">$a$</span>.</p> <p>Now that we know these completion groups of words, it is easy to find the separating words.</p> <p>For example, <span class="math-container">$S_1$</span> and <span class="math-container">$S_2$</span>. We need a word that is in <span class="math-container">$L$</span> or that starts with <span class="math-container">$a$</span> and ends with <span class="math-container">$aa$</span>, but not both. The word <span class="math-container">$abaa$</span> will do.</p> <p>For example, <span class="math-container">$S_5$</span> and <span class="math-container">$S_6$</span>. We need a word that ends with <span class="math-container">$aa$</span> or that ends with <span class="math-container">$a$</span> but not both. The word <span class="math-container">$a$</span> will do.</p>