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 monoidA monoid
M(a set with an associative product and identity) recognizesL ⊆ Σ*if there is a homomorphismh : Σ* → Mand a subsetP ⊆ MwithL = h⁻¹(P). (Σ*under concatenation is the free monoid.)
Regular = recognized by a finite monoid
Lis 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.