Syntactic monoid

From Wikipedia, the free encyclopedia

In mathematics, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L.

1 Syntactic quotient
2 Syntactic equivalence
3 Syntactic monoid
4 Examples

[edit] Syntactic quotient

Given $S\subset M$ a subset 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 $m\in M$ is the set

$S \ / \ m=\{u\in M \;\vert\; um\in S \}$

Similarly, the left quotient is

$m \setminus S=\{u\in M \;\vert\; mu\in S \}$

[edit] Syntactic equivalence

The syntactic quotient induces an equivalence relation on M, called the syntactic relation, or syntactic equivalence or syntactic congruence (induced by S). The right syntactic equivalence is the equivalence relation

$\sim_S \;= \{(s,t)\in M\times M \,\vert\; S \ / \ s = S \ / \ t \}$

Similarly, the left syntactic relation is

$\,_S\sim \;= \{(s,t)\in M\times M \,\vert\; s\setminus S = t \setminus S \}$

A double-sided congruence may be defined as

$u \sim_S v \Leftrightarrow \forall x, y\in M (xuy \in S \Leftrightarrow xvy \in S)$

[edit] Syntactic monoid

The syntactic quotient is compatible with concatenation in the monoid, in that one has

$(M \ / \ s) \ / \ t = M \ / \ (ts)$

for all $s,t\in M$ (and similarly for the left quotient). Thus, the syntactic quotient is a monoid morphism, and induces a quotient monoid

$M(S)= M \ / \ \sim_S$

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

$\{L \ / \ m \,\vert\; m\in M\}$

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 $L \ / \ x\,\sim L \ / \ y$ . Thus, the number of elements in $\{L \ / \ m \,\vert\; m\in M\}$ is just exactly equal to the number of final states of the automaton. Assume the converse: that the number of elements in $\{L \ / \ m \,\vert\; m\in M\}$ is finite. One can then construct an automaton where so that $Q=\{L \ / \ m \,\vert\; m\in M\}$ is the set of states, $F=\{L \ / \ m \,\vert\; m\in L\}$ is the set of final states, the singleton L is the initial state, and the transition function is given by $(L \ / \ x) \ / \ y=L \ / \ (xy)$ . Clearly, this automaton recognizes L. Thus, a language L is recognizable if and only if the set $\{L \ / \ m \,\vert\; m\in M\}$ is finite.

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

[edit] Examples

The bicyclic monoid is the syntactic monoid of the Dyck language (the language of balanced sets of parenthesis).
The trace monoid is an example of a syntactic monoid.