Syntactic monoid

From Wikipedia, the free encyclopedia

In mathematics, the syntactic monoid M(L) of a formal language L over an alphabet A is defined as the quotient M(L) = A^* / ~_L, where ~_L denotes the syntactic congruence of L:

$u \sim_L v \Leftrightarrow \forall x, y\in A^* (xuy \in L \Leftrightarrow xvy \in L)$

It can be shown that the syntactic monoid of L is the smallest monoid that recognizes L; that is, M(L) recognizes L, and for every monoid N recognizing L, M(L) is a quotient of a submonoid of N. The syntactic monoid of L is also the transition monoid of the minimal automaton of L.