Myhill-Nerode theorem for semigroups

Let $S$ be a semigroup.$X\subseteq S$ is recognizableif 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 ${𝒩}_X$ its Nerode equivalence.

Theorem 1 (Myhill-Nerode 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/{𝒩}_X$ is finite.

Theorem 1 generalizes Myhill-Nerode theorem for languagesto 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 aboveif and only if it is recognizable by a DFA.

The equivalence of points 1, 2 and 3is attributed to John Myhill,while the equivalence of points 1, 4 and 5is 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$.

3 $\Rightarrow$ 1.Straightforward from $X$ being union of classes of ${\equiv }_X$.

3 $\Rightarrow$ 4.Straightforward from ${\equiv }_X$ satisfying the second requirement.

4 $\Rightarrow$ 5.Straightforward from the maximality property of Nerode equivalence.

5 $\Rightarrow$ 3.Let

$$S/{𝒩}_X=\{{[{\xi }_1]}_{{𝒩}_X},\mathrm{\dots },{[{\xi }_K]}_{{𝒩}_X}\}.$$(1)

Since $s_1{\equiv }_X{s}_2$ iff $\mathrm{\ell }{s}_1{𝒩}_X\mathrm{\ell }{s}_2$for every $\mathrm{\ell }\in S$,determining ${[s]}_{{\equiv }_X}$is the same as determining ${[\mathrm{\ell }s]}_{{𝒩}_X}$as $\mathrm{\ell }$ varies in $S$,plus the class ${\mathrm{[}s\mathrm{]}}_{{\mathrm{N}}_X}$.(This additional class takes into account the possibilitythat $s\notin {[\mathrm{\ell }s]}_{{𝒩}_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{𝒩}_X{s}_2$ implies $s_{1}t{𝒩}_X{s}_{2}t$,if ${[{\mathrm{\ell }}_1]}_{{𝒩}_X}={[{\mathrm{\ell }}_2]}_{{𝒩}_X}$then ${[{\mathrm{\ell }}_{1}s]}_{{𝒩}_X}={[{\mathrm{\ell }}_{2}s]}_{{𝒩}_X}$ as well.To determine ${[s]}_{{\equiv }_X}$it is thus sufficient to determine the ${[{\xi }_{i}s]}_{{𝒩}_X}$for $1\le i\le K$,plus ${[s]}_{{𝒩}_X}$.

We can thus identify the class ${[s]}_{{\equiv }_X}$with the sequence$({[{\xi }_{1}s]}_{{𝒩}_X},\mathrm{\dots },{[{\xi }_{K}s]}_{{𝒩}_X},{[s]}_{{𝒩}_X}).$Then the number of classes of ${\equiv }_X$cannot exceed that of $(K+1)$-ples of classes of ${𝒩}_X$,which is $K^{K+1}$. $\mathrm{\square }$