Syntactic monoid
|
|
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.