Syntactic monoid

In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L.

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. Given a subset ${\displaystyle S}$ of a free monoid ${\displaystyle M}$, one may define sets that consist of formal left or right inverses of elements in ${\displaystyle S}$. These are called quotients, and one may define right or left quotients, depending on which side one is concatenating. Thus, the right quotient of ${\displaystyle S}$ by an element ${\displaystyle m}$ from ${\displaystyle M}$ is the set

...
Wikipedia