Editing Syntactic monoid (section)

==Syntactic equivalence==
The syntactic quotient induces an [[equivalence relation]] on <math>M</math>, called the '''syntactic relation''', or '''syntactic equivalence'''  (induced by <math>S</math>).

The '''right syntactic equivalence''' is the equivalence relation

:<math>s \sim_S t \ \Leftrightarrow\ S \,/ \,s \;=\; S \,/ \,t \ \Leftrightarrow\ (\forall x\in M\colon\ xs \in S \Leftrightarrow xt \in S)</math>.

Similarly, the '''left syntactic equivalence''' is

:<math>s \;{}_S{\sim}\; t \ \Leftrightarrow\ s \setminus S \;=\; t \setminus S \ \Leftrightarrow\ (\forall y\in M\colon\ sy \in S \Leftrightarrow ty \in S)</math>.

Observe that the ''right'' syntactic equivalence is a ''left'' [[congruence relation|congruence]] with respect to [[string concatenation]] and vice versa; i.e., <math>s \sim_S t \ \Rightarrow\ xs \sim_S xt\ </math> for all <math>x \in M</math>.

The '''syntactic congruence''' or '''[[John Myhill|Myhill]] congruence'''<ref name=Hol160>Holcombe (1982) p.160</ref> is defined as<ref name=Law210>Lawson (2004) p.210</ref>

:<math>s \equiv_S t \ \Leftrightarrow\ (\forall x, y\in M\colon\ xsy \in S \Leftrightarrow xty \in S)</math>.

The definition extends to a congruence defined by a subset <math>S</math> of a general monoid <math>M</math>.  A '''disjunctive set''' is a subset <math>S</math> such that the syntactic congruence defined by <math>S</math> is the equality relation.<ref name=Law232>Lawson (2004) p.232</ref>

Let us call <math>[s]_S</math> the equivalence class of <math>s</math> for the syntactic congruence.
The syntactic congruence is [[Quotient (universal algebra)|compatible]] with concatenation in the monoid, in that one has

:<math>[s]_S[t]_S=[st]_S</math>

for all <math>s,t\in M</math>. Thus, the syntactic quotient is a [[monoid morphism]], and induces a [[quotient monoid]]

:<math>M(S)= M \ / \ {\equiv_S}</math>.

This monoid <math>M(S)</math> is called the '''syntactic monoid''' of <math>S</math>.
It can be shown that it is the smallest [[monoid]] that [[recognizable set|recognizes]] <math>S</math>; that is, <math>M(S)</math> recognizes <math>S</math>, and for every monoid <math>N</math> recognizing <math>S</math>, <math>M(S)</math> is a quotient of a [[submonoid]] of <math>N</math>. The syntactic monoid of <math>S</math> is also the [[transition monoid]] of the [[minimal automaton]] of <math>S</math>.<ref name=Hol160/><ref name=Law210/><ref name=S55>Straubing (1994) p.55</ref>

A '''group language''' is one for which the syntactic monoid is a [[Group (mathematics)|group]].<ref name=Sak342>Sakarovitch (2009) p.342</ref>