Syntactic monoid
Encyclopedia
In mathematics
and computer science
, the syntactic monoid M(L) of a formal language
L is the smallest monoid
that recognizes
the language L.
of a monoid M, one may define sets that consist of formal left or right inverses of elements in 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 S by an element
is the set
Similarly, the left quotient is
on M, called the syntactic relation, or syntactic equivalence or syntactic congruence (induced by S). The right syntactic equivalence is the equivalence relation
Similarly, the left syntactic relation is
A double-sided congruence may be defined as
with concatenation in the monoid, in that one has
for all
(and similarly for the left quotient). Thus, the syntactic quotient is a monoid morphism, and induces a quotient monoid
It can be shown that the syntactic monoid of S is the smallest monoid
that recognizes
S ; that is, M(S) recognizes S, and for every monoid N recognizing S, M(S) is a quotient of a submonoid of N. The syntactic monoid of S is also the transition monoid of the minimal automaton of S.
Equivalently, a language L is recognizable if and only if the family of quotients
is finite. The proof showing equivalence is quite easy. Assume that a string x is recognizable by a deterministic finite state machine
, with the final state of the machine being f. If y is another string recognized by the machine, also terminating in the same final state f, then clearly one has
. Thus, the number of elements in 
is just exactly equal to the number of final states of the automaton. Assume the converse: that the number of elements in 
is finite. One can then construct an automaton where so that 
is the set of states, 
is the set of final states, the language L is the initial state, and the transition function is given by 
. Clearly, this automaton recognizes L. Thus, a language L is recognizable if and only if the set 
is finite.
Given a regular expression
E representing S, it is easy to compute the syntactic monoid of S.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the syntactic monoid M(L) of a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
L is the smallest monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
that recognizes
Recognizable language
In mathematics and computer science, a recognizable language is a formal language that is recognized by a finite state machine. Equivalently, a recognizable language is one for which the family of quotients for the syntactic relation is finite.-Definition:...
the language L.
Syntactic quotient
Given of a monoid M, one may define sets that consist of formal left or right inverses of elements in S. These are called quotientsString operations
In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used on computer programming, and some commonly used functions in the theoretical realm are rarely used when programming...
, and one may define right or left quotients, depending on which side one is concatenating. Thus, the right quotient of S by an element
is the setSimilarly, the left quotient is
Syntactic equivalence
The syntactic quotient induces an equivalence relationEquivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
on M, called the syntactic relation, or syntactic equivalence or syntactic congruence (induced by S). The right syntactic equivalence is the equivalence relation
Similarly, the left syntactic relation is
A double-sided congruence may be defined as
Syntactic monoid
The syntactic quotient is compatibleQuotient algebra
In mathematics, a quotient algebra, , also called a factor algebra is obtained by partitioning the elements of an algebra in equivalence classes given by a congruence, that is an equivalence relation that is additionally compatible with all the operations of the algebra, in the formal sense...
with concatenation in the monoid, in that one has
for all
(and similarly for the left quotient). Thus, the syntactic quotient is a monoid morphism, and induces a quotient monoidIt can be shown that the syntactic monoid of S is the smallest monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
that recognizes
Recognizable language
In mathematics and computer science, a recognizable language is a formal language that is recognized by a finite state machine. Equivalently, a recognizable language is one for which the family of quotients for the syntactic relation is finite.-Definition:...
S ; that is, M(S) recognizes S, and for every monoid N recognizing S, M(S) is a quotient of a submonoid of N. The syntactic monoid of S is also the transition monoid of the minimal automaton of S.
Equivalently, a language L is recognizable if and only if the family of quotients
is finite. The proof showing equivalence is quite easy. Assume that a string x is recognizable by a deterministic finite state machine
Deterministic finite state machine
In the theory of computation and automata theory, a deterministic finite state machine—also known as deterministic finite automaton —is a finite state machine accepting finite strings of symbols. For each state, there is a transition arrow leading out to a next state for each symbol...
, with the final state of the machine being f. If y is another string recognized by the machine, also terminating in the same final state f, then clearly one has
. Thus, the number of elements in is just exactly equal to the number of final states of the automaton. Assume the converse: that the number of elements in is finite. One can then construct an automaton where so that is the set of states, is the set of final states, the language L is the initial state, and the transition function is given by . Clearly, this automaton recognizes L. Thus, a language L is recognizable if and only if the set is finite.Given a regular expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
E representing S, it is easy to compute the syntactic monoid of S.
Examples
- The bicyclic monoid is the syntactic monoid of the Dyck languageDyck languageIn the theory of formal languages of computer science, mathematics, and linguistics, the Dyck language is the language consisting of balanced strings of parentheses [ and ]. It is important in the parsing of expressions that must have a correctly nested sequence of parentheses, such as arithmetic...
(the language of balanced sets of parentheses). - The trace monoidTrace monoidIn mathematics and computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place...
is an example of a syntactic monoid.