Discrete Algebraic Methods

If, on the other hand, a language L is recognized by a homomorphism to any finite semigroup, then L is also recognized by μL. This is shown next.

Lemma 7.58. Let L ⊆ Σω and let φ: Σ+ → S be a homomorphism to a finite semigroup S recognizing L. Then μL : Σ+ → Synt(L) recognizes the language L and φ(u) ↦ μL(u) defines a surjective homomorphism from the subsemigroup φ(Σ+)⊆ S onto Synt(L).

Proof: First, we show that the mapping φ(u) ↦ μL(u) is well defined. Let φ(u) = φ(υ). We obtain

where the last equivalence in both lines uses φ(u) = φ(υ). Thus, φ(u) = φ(υ) implies u ≡L υ. As a consequence, μL induces a well-defined surjective homomorphism

Next, ...