Syntactic monoid

From Free net 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:

<math>u \sim_L v \Leftrightarrow \forall x, y\in A^* (xuy \in L \Leftrightarrow xvy \in L)</math>

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.

Given a regular expression E representing L, it is easy to compute the syntactic monoid of L.