In mathematics and computer science, the syntactic monoid
is the minimal monoid that recognizes the language
By the Myhill–Nerode theorem, the syntactic monoid is unique up to unique isomorphism.
An alphabet is a finite set.
The free monoid on a given alphabet 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.
of a free monoid
, 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 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
[1][2][4] A group language is one for which the syntactic monoid is a group.