Syntactic Semigroup

For the alphabet A the set of all words A^* is a free monoid with a generating set A and catenation of words as operation.

Let L be a subset of A^* and $x\in A^*$. We define context of x with respect to L to be $C(x)=\{\,(y,z)\,\vert\,y,z\in A^*,\,yxz \in L\,\}$.

Definition The syntactic congruence of L is the relation:

$$\mbox { For every } x,y\in A^*,\,\,\, x\equiv y \Leftrightarrow C(x)=C(y).$$

The syntactic monoid Syn(L) of L is the monoid $A^*/_\equiv$. For $x\in A^*$, the element of Syn(L) with representative x will be written as [x]. The operation in Syn(L) is defined with $[x]\,[y]=[xy]$.

Note 1.3.5 It is well known fact (see for ex. [11], or [15]) that L is a regular language iff Syn(L) is finite. So, the factor language of every sofic system has a finite syntactic monoid.