Science Fair Project Encyclopedia
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:
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.
Last updated: 08-07-2005 16:02:38
03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details