scratch

§ Alternative Version of Myhill-Nerode

created 2021-08-25
  • In one version of myhill-nerode I know, the states correspond to equivalence classes of strings under the equivalence relation x∼yx \sim yx∼yiff forall strings sss, x+s∈L  ⟺  y+s∈Lx + s \in L \iff y + s \in Lx+s∈L⟺y+s∈L.
  • In another version (V2), we define the right context of a string www to be the set of all suffixes sss such that w+s∈Lw + s \in Lw+s∈L. That is, R(w)≡{s∈A∗:w+s∈L}R(w) \equiv \{ s \in A^* : w + s \in L \}R(w)≡{s∈A∗:w+s∈L}.
  • This induces an equivalence relation where x∼yx \sim yx∼y iff R(x)=R(y)R(x) = R(y)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.
❦
Newer ৪ Blog ৪ Older