§ 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.