There are two other forms of the Myhill-Nerode theorem. One of these can be proved by applying the previous version to the reversed language. The reversed language is regular if and only if the original one is. In this second version of the Myhill-Nerode theorem the set which we need to be finite is the set of equivalence classes for the relation where \({ u }\) and \({ v }\) are equivalent if and only if \[ \{ z ∈ B : z u ∈ L \} = \{ z ∈ B : z v ∈ L \} . \] This is the same condition as in the definition of \({ E }\), except that the order of the concatenations has been reversed.
This form of the Myhill-Nerode theorem is somewhat less interesting than the previous one, since it doesn’t lead to the construction of a deterministic finite state automaton in the case where the grammar is regular.
There’s a third version of Myhill-Nerode, which does construct a strongly deterministic finite state automaton in the regular case. This finite state automaton is not minimal in general but it does have one interesting property which the one we constructed earlier lacks. Strong determinism means that if we know the current state and the next input token then we know the next state. This new finite state automaton has the additional property that if we know the current state and the last input token read then we know the previous state.
The third version of Myhill-Nerode is based on continuations and equivalence classes, but instead of consider right continuations, as in the first version, or left continuations, as in the second version, we consider bidirectional continuations.
For any list \({ w }\) we say that \({ ( u , z ) }\) is a bidirectional continuation of \({ w }\) if \({ u w z ∈ L }\). We say that \({ w }\) and \({ x }\) are bidirectionally equivalent if they have the same set of bidirectional continuations. Bidirectionally equivalent lists are equivalent in the sense we considered earlier but the converse generally isn’t true. The third version of the Myhill-Nerode theorem says that the language is regular if and only if the set of bidirectional equivalence classes is finite.
Bidirectional equivalence has one important property which ordinary equivalence lacks. If \({ u }\) is bidirectionally equivalent to \({ x }\) and \({ v }\) is bidirectionally equivalent to \({ y }\) then \({ u v }\) is bidirectionally equivalent to \({ x y }\). This allows us to perform the quotient construction on \({ B }\) considered as a monoid with concatenation as the operation. The quotient is called the syntactic monoid of the language. Various properties of the language can be defined in terms of the syntactic monoid. The advantage of doing this is that there is only one syntactic monoid for a language. If we try to define properties of a language in terms of the structure of its grammar we need to show that we get the same result regardless of which grammar is used. Similarly, if we try to define properties of a language in terms of the structure of a finite state automaton then we need to show that we get the same result regardless of which automaton is used. The same problem arises if we try to define properties in terms of regular expressions, but not if we define them in terms of the syntactic monoid.