In mathematics and computer science, the syntactic monoid
is the smallest monoid that recognizes the language
The free monoid on a given set is the monoid whose elements are all the strings of zero or more elements from that set, with string concatenation as the monoid operation and the empty string as the identity element.
, one may define sets that consist of formal left or right inverses of elements in
These are called quotients, and one may define right or left quotients, depending on which side one is concatenating.
is the set Similarly, the left quotient is The syntactic quotient[clarification needed] induces an equivalence relation on
, called the syntactic relation, or syntactic equivalence (induced by
The right syntactic equivalence is the equivalence relation Similarly, the left syntactic equivalence is Observe that the right syntactic equivalence is a left congruence with respect to string concatenation and vice versa; i.e.,
The syntactic congruence or Myhill congruence[1] is defined as[2] The definition extends to a congruence defined by a subset
A disjunctive set is a subset
such that the syntactic congruence defined by
The syntactic congruence is compatible with concatenation in the monoid, in that one has for all
Thus, the syntactic quotient is a monoid morphism, and induces a quotient monoid This monoid
is called the syntactic monoid of
It can be shown that it is the smallest monoid that recognizes
is also the transition monoid of the minimal automaton of
[5] The Myhill–Nerode theorem states: a language
is regular if and only if the family of quotients
has finite index (meaning it partitions
into finitely many equivalence classes).
[6] This theorem was first proved by Anil Nerode (Nerode 1958) and the relation
is thus referred to as Nerode congruence by some authors.
Assume that a finite automaton recognizing
is another string read by the machine, also terminating in the same state
is at most equal to the number of states of the automaton and
is at most the number of final states.
For a proof of the "if" part, assume that the number of elements in
is the set of final states, the language
is the initial state, and the transition function is given by
Note that this proof also builds the minimal automaton.