Syntactic monoid

Summary

The syntactic monoid of a formal language $L$ is a quotient of the free monoid of all words. One divides by the coarsest congruence that does not mix words of $L$ with words outside $L$. It is the smallest monoid that recognizes $L$. A language is regular exactly when its syntactic monoid is finite. Algebraic properties of this monoid classify regular languages; for instance Schützenberger's theorem characterizes the star-free languages by it.