Myhill-Nerode theorem for semigroups


Let S be a semigroupPlanetmathPlanetmath. X⊆S is recognizable if it is union of classes of a congruencePlanetmathPlanetmathPlanetmathPlanetmath χ such that S/χ is finite.

In the rest of the entry, ≡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⊆S. The following are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath.

  1. 1.

    X is recognizable.

  2. 2.

    There exist a finite semigroup T and a morphism ϕ:S→T such that X=ϕ-1⁢(ϕ⁢(X)).

  3. 3.

    The syntactic semigroup of X is finite.

  4. 4.

    There exists an equivalence relation ∼ on S such that

    • –

      S/∼ is finite and

    • –

      s1∼s2 implies s1⁢t∼s2⁢t.

  5. 5.

    The quotient set S/𝒩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 languagePlanetmathPlanetmath 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 ⇒ 2. Given a congruence χ such that |S/χ|<∞ and X is union of classes of χ, choose T as the quotient semigroup S/χ and ϕ as the natural homomorphismMathworldPlanetmath mapping s to [s]χ.

2 ⇒ 3. Given a morphism of semigroups ϕ:S→T with T finite and X=ϕ-1⁢(ϕ⁢(X)), put s⁢χ⁢t iff ϕ⁢(s)=ϕ⁢(t).

Since ϕ is a morphism, χ is a congruence; moreover, X=ϕ-1⁢(ϕ⁢(X)) means that X is union of classes of χ-equivalence. By the maximality property of syntactic congruence, the number of classes of ≡X does not exceed the number of classes of χ, which in turn does not exceed the number of elements of T.

3 ⇒ 1. Straightforward from X being union of classes of ≡X.

3 ⇒ 4. Straightforward from ≡X satisfying the second requirement.

4 ⇒ 5. Straightforward from the maximality property of Nerode equivalence.

5 ⇒ 3. Let

S/𝒩X={[ξ1]𝒩X,…,[ξK]𝒩X}. (1)

Since s1≡Xs2 iff ℓ⁢s1⁢𝒩X⁢ℓ⁢s2 for every ℓ∈S, determining [s]≡X is the same as determining [ℓ⁢s]𝒩X as ℓ varies in S, plus the class [s]NX. (This additional class takes into account the possibility that s∉[ℓ⁢s]𝒩X for any ℓ∈S, which cannot be excluded a priori: do not forget that S is not required to be a monoid.)

But since s1⁢𝒩X⁢s2 implies s1⁢t⁢𝒩X⁢s2⁢t, if [ℓ1]𝒩X=[ℓ2]𝒩X then [ℓ1⁢s]𝒩X=[ℓ2⁢s]𝒩X as well. To determine [s]≡X it is thus sufficient to determine the [ξi⁢s]𝒩X for 1≤i≤K, plus [s]𝒩X.

We can thus identify the class [s]≡X with the sequence ([ξ1⁢s]𝒩X,…,[ξK⁢s]𝒩X,[s]𝒩X). Then the number of classes of ≡X cannot exceed that of (K+1)-ples of classes of 𝒩X, which is KK+1. □

References

A. de Luca and S. Varricchio. Finiteness and Regularity in Semigroups and Formal LanguagesMathworldPlanetmath. Springer Verlag, Heidelberg 1999.

Title Myhill-Nerode theorem for semigroups
Canonical name MyhillNerodeTheoremForSemigroups
Date of creation 2014-05-14 17:29:14
Last modified on 2014-05-14 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