MyhillNerode theorem for semigroups
Let $S$ be a semigroup^{}. $X\subseteq S$ is recognizable if it is union of classes of a congruence^{} $\chi $ such that $S/\chi $ is finite.
In the rest of the entry, ${\equiv}_{X}$ will be the syntactic congruence of $X$, and ${\mathcal{N}}_{X}$ its Nerode equivalence.
Theorem 1 (MyhillNerode theorem for semigroups)
Let $S$ be a semigroup and let $X\mathrm{\subseteq}S$. The following are equivalent^{}.

1.
$X$ is recognizable.

2.
There exist a finite semigroup $T$ and a morphism $\varphi :S\to T$ such that $X={\varphi}^{1}(\varphi (X))$.

3.
The syntactic semigroup of $X$ is finite.

4.
There exists an equivalence relation $\sim $ on $S$ such that

–
$S/\sim $ is finite and

–
${s}_{1}\sim {s}_{2}$ implies ${s}_{1}t\sim {s}_{2}t$.

–

5.
The quotient set $S/{\mathcal{N}}_{X}$ is finite.
Theorem 1 generalizes MyhillNerode theorem for languages to subsets of generic, not necessarily free, semigroups. In fact, as a consequence of Theorem 1, a language^{} on a finite alphabet is recognizable in the sense given above if and only if it is recognizable by a DFA.
The equivalence of points 1, 2 and 3 is attributed to John Myhill, while the equivalence of points 1, 4 and 5 is attributed to Anil Nerode.
Proof of Theorem 1.
1 $\Rightarrow $ 2. Given a congruence $\chi $ such that $$ and $X$ is union of classes of $\chi $, choose $T$ as the quotient semigroup $S/\chi $ and $\varphi $ as the natural homomorphism^{} mapping $s$ to ${[s]}_{\chi}$.
2 $\Rightarrow $ 3. Given a morphism of semigroups $\varphi :S\to T$ with $T$ finite and $X={\varphi}^{1}(\varphi (X))$, put $s\chi t$ iff $\varphi (s)=\varphi (t)$.
Since $\varphi $ is a morphism, $\chi $ is a congruence; moreover, $X={\varphi}^{1}(\varphi (X))$ means that $X$ is union of classes of $\chi $equivalence. By the maximality property of syntactic congruence, the number of classes of ${\equiv}_{X}$ does not exceed the number of classes of $\chi $, which in turn does not exceed the number of elements of $T$.
$$S/{\mathcal{N}}_{X}=\{{[{\xi}_{1}]}_{{\mathcal{N}}_{X}},\mathrm{\dots},{[{\xi}_{K}]}_{{\mathcal{N}}_{X}}\}.$$  (1) 
Since ${s}_{1}{\equiv}_{X}{s}_{2}$ iff $\mathrm{\ell}{s}_{1}{\mathcal{N}}_{X}\mathrm{\ell}{s}_{2}$ for every $\mathrm{\ell}\in S$, determining ${[s]}_{{\equiv}_{X}}$ is the same as determining ${[\mathrm{\ell}s]}_{{\mathcal{N}}_{X}}$ as $\mathrm{\ell}$ varies in $S$, plus the class ${\mathrm{[}s\mathrm{]}}_{{\mathrm{N}}_{X}}$. (This additional class takes into account the possibility that $s\notin {[\mathrm{\ell}s]}_{{\mathcal{N}}_{X}}$ for any $\mathrm{\ell}\in S$, which cannot be excluded a priori: do not forget that $S$ is not required to be a monoid.)
But since ${s}_{1}{\mathcal{N}}_{X}{s}_{2}$ implies ${s}_{1}t{\mathcal{N}}_{X}{s}_{2}t$, if ${[{\mathrm{\ell}}_{1}]}_{{\mathcal{N}}_{X}}={[{\mathrm{\ell}}_{2}]}_{{\mathcal{N}}_{X}}$ then ${[{\mathrm{\ell}}_{1}s]}_{{\mathcal{N}}_{X}}={[{\mathrm{\ell}}_{2}s]}_{{\mathcal{N}}_{X}}$ as well. To determine ${[s]}_{{\equiv}_{X}}$ it is thus sufficient to determine the ${[{\xi}_{i}s]}_{{\mathcal{N}}_{X}}$ for $1\le i\le K$, plus ${[s]}_{{\mathcal{N}}_{X}}$.
We can thus identify the class ${[s]}_{{\equiv}_{X}}$ with the sequence $({[{\xi}_{1}s]}_{{\mathcal{N}}_{X}},\mathrm{\dots},{[{\xi}_{K}s]}_{{\mathcal{N}}_{X}},{[s]}_{{\mathcal{N}}_{X}}).$ Then the number of classes of ${\equiv}_{X}$ cannot exceed that of $(K+1)$ples of classes of ${\mathcal{N}}_{X}$, which is ${K}^{K+1}$. $\mathrm{\square}$
References
A. de Luca and S. Varricchio. Finiteness and Regularity in Semigroups and Formal Languages^{}. Springer Verlag, Heidelberg 1999.
Title  MyhillNerode theorem for semigroups 

Canonical name  MyhillNerodeTheoremForSemigroups 
Date of creation  20140514 17:29:14 
Last modified on  20140514 17:29:14 
Owner  Ziosilvio (18733) 
Last modified by  Ziosilvio (18733) 
Numerical id  5 
Author  Ziosilvio (18733) 
Entry type  Theorem 
Classification  msc 20M35 
Classification  msc 68Q70 
Defines  recognizable subset of a semigroup 