Combinatorial and Automata Applications

Syntactic Monoids and Kleene's Theorem

Every recognisable language has a smallest monoid recognising it. Properties of that monoid correspond to properties of the language, and the correspondence is a variety theorem.

Engineering · Mathematics5 min readKV-MATH-0231

Learning objectives

Define the syntactic congruence and construct the syntactic monoid.
Distinguish the syntactic monoid from the transition monoid.
State Kleene's theorem in both directions.
State Schützenberger's characterisation of star-free languages.
Explain the Eilenberg correspondence between language and monoid varieties.
Recognise this as the source's predicted 'applied universal algebra'.

01The syntactic congruence

The Myhill–Nerode relation is a right congruence. Making it two-sided gives the syntactic congruence, which is the coarsest congruence on the free monoid saturating the language.

u ~_L v ⟺ for all x, y ∈ Σ*: xuy ∈ L if and only if xvy ∈ L

Two-sided: compatible with multiplication on both sides, hence a genuine monoid congruence rather than merely a right congruence.

Myhill–Nerode ≡_L

Right congruence

Suffixes only. Its index is the state count of the minimal acceptor. Gives the minimal automaton.

Syntactic ~_L

Two-sided congruence

Contexts on both sides. Its index is the size of the syntactic monoid. Gives the minimal recognising monoid.

The syntactic congruence refines the Myhill–Nerode relation, so the syntactic monoid is at least as large as the minimal automaton's state set — often considerably larger.

02The syntactic monoid

M(L) := Σ*/~_L is the syntactic monoid of L. It is finite exactly when L is recognisable, and it is the smallest monoid recognising L in a precise sense.

Key resultUniversal property of the syntactic monoid

A monoid M recognises L when there is a homomorphism φ : Σ* → M and a subset P ⊆ M with L = φ⁻¹(P). The syntactic monoid recognises L, and every monoid recognising L has M(L) as a quotient of a submonoid. So M(L) divides every recogniser — it is minimal for the division ordering.

Division — being a quotient of a submonoid — is the right ordering here rather than the subobject or quotient ordering alone, and it is exactly the ordering used in the Eilenberg correspondence below. Note that division is precisely membership in HS, two of the three class operators.

03Kleene's theorem

Kleene's 1956 result identifies the languages accepted by finite acceptors with those built from finite languages by three operations.

Key resultKleene's theorem

A language is recognisable by a finite acceptor if and only if it is regular — that is, obtainable from finite languages using union, concatenation and Kleene star finitely many times.

Regular ⟹ recognisable
By structural induction on the regular expression, using the closure constructions from the previous page. Each operation has an acceptor construction.
Recognisable ⟹ regular
By induction on the state set, expressing the language of paths between two states avoiding a given set of intermediate states. The Kleene star appears exactly when a loop is eliminated.
Third equivalent
Finite index of the Myhill–Nerode relation, from the previous page. Three characterisations of one class.
Fourth equivalent
Recognition by a finite monoid. This is the form that generalises.

The monoid formulation is the one that opens the door to further classification. Once a language is identified with a finite monoid plus a subset, subclasses of languages correspond to classes of finite monoids, and monoid classes are exactly what universal algebra knows how to handle.

04Schützenberger's star-free theorem

Star-free languages are those expressible using union, concatenation and complement but no Kleene star. Schützenberger characterised them algebraically in 1965.

Key resultSchützenberger's theorem

A recognisable language is star-free if and only if its syntactic monoid is aperiodic — contains no non-trivial subgroup, equivalently satisfies xⁿ ≈ xⁿ⁺¹ for some n.

This is a genuinely surprising result. A syntactic restriction on how the language may be written corresponds exactly to an equational property of an associated finite algebra. Aperiodicity is checkable by inspecting the monoid; star-freeness is not obviously checkable at all from the language description.

Language classes and their monoid characterisations
Language class	Syntactic monoid condition
Recognisable (regular)	finite
Star-free	aperiodic (group-free)
Piecewise testable	J-trivial
Locally testable	locally idempotent and commutative
Definite	satisfies a right-zero condition

Each row is a theorem, and each was proved by finding the right equational condition. The pattern generalises, which is Eilenberg's contribution.

05The Eilenberg correspondence

Eilenberg observed that these results are instances of a single bijection between classes of languages and classes of finite monoids.

Variety of languages

Closed under Boolean ops, quotients, inverse homomorphisms

A family assigning to each alphabet a set of languages, closed under the appropriate operations.

Pseudovariety of monoids

Closed under division and finite products

A class of finite monoids closed under submonoids, quotients and finite direct products — the finite analogue of a variety.

NoteWhy pseudovarieties rather than varieties

Restricting to finite monoids breaks closure under infinite products, so a pseudovariety is closed under finite products only. Reiterman's theorem supplies the corresponding equational characterisation using profinite identities rather than ordinary ones — a genuine extension of Birkhoff's theorem to the finite setting, and one that postdates the source.

The correspondence is a bijection: every variety of languages corresponds to exactly one pseudovariety of finite monoids and conversely. Kleene's theorem is the top of the lattice; Schützenberger's is one specific pair; and the classification of the whole lattice is an active programme.

06The source's prediction

The preface predicts that 'applied universal algebra' would become much more prominent. Chapter III's two examples — the refutation of Euler's conjecture and Kleene's characterisation — were offered as evidence.

1956–1965
Kleene and Schützenberger
The foundational results, both present in the source.
1976
Eilenberg's correspondence
Systematises them into a bijection between language and monoid classes. Cited in the source's Recent Developments section §6.
1982
Reiterman's theorem
Profinite equational characterisation of pseudovarieties — the finite-algebra analogue of Birkhoff's theorem. Roughly contemporary with the source and not covered by it.
Post-source
The algebraic approach to constraint satisfaction
The same method — classify a computational problem by the algebra of its polymorphisms — applied to CSP, culminating in the dichotomy theorem. Flagged as beyond the source and treated in the Research Frontier stream.

The prediction was correct, and the CSP dichotomy is its largest vindication: an entire complexity classification driven by Mal'cev conditions on an associated algebra. That development is covered in this collection's Research Frontier stream and marked as postdating the 1981 text.

Frequently asked

Is the syntactic monoid always bigger than the minimal automaton?

At least as big, and often much bigger — the syntactic monoid can be exponential in the state count. They coincide only in special cases. The trade-off is that the monoid carries strictly more information, which is what makes the finer classifications possible.

Can I compute the syntactic monoid from an acceptor?

Yes. Take the transition monoid of the minimal acceptor — the monoid of all maps δ_w on the state set — and it equals the syntactic monoid when the acceptor is minimal and all states are reachable. This is the standard computation and is implemented in automata libraries.

Does the Eilenberg correspondence hold for infinite monoids?

The correspondence as stated is between varieties of recognisable languages and pseudovarieties of finite monoids, so finiteness is built in. Extensions to broader settings exist but lose the clean bijection. The finiteness restriction is what forces profinite rather than ordinary identities in Reiterman's theorem.

Sources and further reading

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
G. Grätzer, Universal Algebra, 2nd edition, Springer.
R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.

Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.