Myhill-Nerode theorem for semigroups

In the rest of the entry, $\equiv_{X}$ will be the syntactic congruence of $X$, and $\mathcal{N}_{X}$ its Nerode equivalence.

Theorem 1 (Myhill-Nerode theorem for semigroups)

Let $S$ be a semigroup and let $X\subseteq S$. The following are equivalent     .

1. 1.

$X$ is recognizable.

2. 2.

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

3. 3.

The syntactic semigroup of $X$ is finite.

4. 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. 5.

The quotient set $S/\mathcal{N}_{X}$ is finite.

Theorem 1 generalizes Myhill-Nerode 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 $|S/\chi|<\infty$ and $X$ is union of classes of $\chi$, choose $T$ as the quotient semigroup $S/\chi$ and $\phi$ as the natural homomorphism  mapping $s$ to $[s]_{\chi}$.

2 $\Rightarrow$ 3. Given a morphism of semigroups $\phi:S\to T$ with $T$ finite and $X=\phi^{-1}(\phi(X))$, put $s\chi t$ iff $\phi(s)=\phi(t)$.

Since $\phi$ is a morphism, $\chi$ is a congruence; moreover, $X=\phi^{-1}(\phi(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/\mathcal{N}_{X}=\left\{[\xi_{1}]_{\mathcal{N}_{X}},\ldots,[\xi_{K}]_{% \mathcal{N}_{X}}\right\}\;.$ (1)

Since $s_{1}\equiv_{X}s_{2}$ iff $\ell s_{1}\mathcal{N}_{X}\ell s_{2}$ for every $\ell\in S$, determining $[s]_{\equiv_{X}}$ is the same as determining $[\ell s]_{\mathcal{N}_{X}}$ as $\ell$ varies in $S$, plus the class $[s]_{\mathcal{N}_{X}}$. (This additional class takes into account the possibility that $s\not\in[\ell s]_{\mathcal{N}_{X}}$ for any $\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 $[\ell_{1}]_{\mathcal{N}_{X}}=[\ell_{2}]_{\mathcal{N}_{X}}$ then $[\ell_{1}s]_{\mathcal{N}_{X}}=[\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\leq i\leq K$, plus $[s]_{\mathcal{N}_{X}}$.

We can thus identify the class $[s]_{\equiv_{X}}$ with the sequence $\left([\xi_{1}s]_{\mathcal{N}_{X}},\ldots,[\xi_{K}s]_{\mathcal{N}_{X}},[s]_{% \mathcal{N}_{X}}\right).$ 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}$. $\Box$

References

Title Myhill-Nerode theorem for semigroups MyhillNerodeTheoremForSemigroups 2014-05-14 17:29:14 2014-05-14 17:29:14 Ziosilvio (18733) Ziosilvio (18733) 5 Ziosilvio (18733) Theorem msc 20M35 msc 68Q70 recognizable subset of a semigroup