## § Alternative version of Myhill-Nerode

- In one version of myhill-nerode I know, the states correspond to equivalence classes of strings under the equivalence relation $x \sim y$iff forall strings $s$, $x + s \in L \iff y + s \in L$.
- In another version (V2), we define the
*right context * of a string $w$ to be the set of all suffixes $s$ such that $w + s \in L$. That is, $R(w) \equiv \{ s \in A^* : w + s \in L \}$. - This induces an equivalence relation where $x \sim y$ iff $R(x) = R(y)$.
- In this version (V2), the states are the right contexts of all strings in the language.
- The transitions are given by concatenating strings in the set with the new character.
- The initial string corresponds to the right context of the empty word.
- The accepting states are those which correspond to right contexts of words in the language.
- This version is much more explicit for computational purposes! We can use it to think about what the automata looks like for small languages, in particular for the suffix automata.