The syntactic monoid — the algebraic face

Parent: regular-equivalences

Regularity as pure algebra: a language is regular iff a finite algebraic object recognizes it.

Recognition by a monoid

A monoid M (a set with an associative product and identity) recognizes L ⊆ Σ* if there is a homomorphism h : Σ* → M and a subset P ⊆ M with L = h⁻¹(P). (Σ* under concatenation is the free monoid.)

Regular = recognized by a finite monoid

L is regular iff it is recognized by a finite monoid. The smallest one is the syntactic monoid (the transition monoid of the minimal DFA / the quotient by the syntactic congruence — the two-sided refinement of Myhill–Nerode).

Why the algebra is worth it

The monoid's structure classifies sub-families that automata/regex can't see cleanly:

• Schützenberger (1965): a language is star-free (definable without *, using complement) iff its syntactic monoid is aperiodic (no nontrivial group inside).
• McNaughton–Papert: star-free = first-order definable (the FO fragment of MSO).

So an algebraic property (aperiodicity) = a logical property (first-order) = an expression property (star-free). This is Eilenberg's variety theory: families of languages correspond to families of finite monoids. The coincidence goes all the way down.