Let $\Sigma = \{ a, b, c\}$, $$ L = \{w\in\Sigma^*\mid w \text{ starts with $ab$ and ends with $ab$}\}, $$ i.e. $L = ab(\varepsilon + (a+b)^*ab)=ab+ab(a+b)^*ab$. I need to find a regular expression for each of the equivalence classes for $R_L$ and find a word, $w\in\Sigma^*$, to differentiate between the classes.
I found the following classes
- $S_1 = (b + c)(a + b + c)^* + a(a + c)(a + b + c)^*$
- $S_2 = ab(a + b + c)^*a$
- $S_3 = ab(a + b + c)^*(bb + c)$
- $S_4 = ab$
- $S_5 = ab(a + b + c)^*ab$
$S_1$ have all the words that cannot be in $L$ so any $w\in\Sigma^*$ will suffice as for any $x\in S_1$, $xw\not\in L$.
For $S_2$ and $S_3$/$S_4$/$S_5$ the word, $w=b$, differentiates because for each $x\in S_2$, $y\in S_3\cup S_4 \cup S_5$, $xw\in L$ but $yb\not \in L$.
For $S_3$ the word $w=\varepsilon$ differentiates it from $S_4$/$S_5$.
Now I have two problems I haven't figured out yet:
- $S_4$ and $S_5$ seems to be equivalent
- where does $\varepsilon$ go
For the first problem it seems that they are indeed equivalent, because for each $w\in\Sigma^*$ and $x\in S_4$, $y\in S_5$, $xw\in L \iff yw\in L$, though I'm not sure because all the examples I have with similar languages where $L = u+v$ ($u, v$ regular expressiosn), put $u$ and $v$ in separate equivalence classes.
As for the second problem, I'm not sure what to do, I can find $w$ such that $\varepsilon$ isn't part of any of the equivalence classes ($w=ab$ for $S_1$, $w=b$ for $S_2$, and $w=cab$ for $S_3$/$S_4$/$S_5$), but then I have an equivalence class with only $\varepsilon$