§ 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 iff forall strings , .
- In another version (V2), we define the right context of a string to be the set of all suffixes such that . That is, .
- This induces an equivalence relation where iff .
- 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.