Selected Topics and Applications
The Syntactic Monoid and Kleene's Theorem
The monoid canonically associated with a language, Kleene's characterisation of the recognisable languages as the regular ones, and the algebraic classification programme this opens.
Learning objectives
- Construct the syntactic monoid of a language
- State Kleene's theorem
- Describe how algebraic properties of the monoid classify languages
The syntactic monoid
For L ⊆ Σ*, the syntactic monoid is the quotient Σ*/≡L of the free monoid by the syntactic congruence.
It is the smallest monoid recognising L, in the sense that any monoid recognising L maps onto it. By Myhill–Nerode it is finite exactly when L is recognisable.
The syntactic monoid together with the image of L in it determines L completely. So questions about the language become questions about a finite monoid with a distinguished subset.
Kleene's theorem
A language built from the finite languages using union, concatenation and the Kleene star operation.
A language is recognisable by a finite state acceptor if and only if it is regular.
The theorem links a machine model to a closure-theoretic description. Combined with Myhill–Nerode, three descriptions coincide:
Proving that recognisable implies regular is where the algebraic view helps: one decomposes the transition structure of the finite algebra, and the regular expression is read off the decomposition. The converse direction is a straightforward construction of acceptors for each operation.
Classification by monoid properties
Once a language is represented by a finite monoid, algebraic conditions on that monoid correspond to descriptive classes of languages. This is the Eilenberg correspondence, and it is the mature form of the programme Chapter III gestures toward.
| Syntactic monoid is | Language class |
|---|---|
| Aperiodic (contains no non-trivial group) | Star-free languages — Schützenberger's theorem |
| A group | Group languages |
| Idempotent and commutative | Piecewise testable — Simon's theorem |
| J-trivial | Piecewise testable |
| Finite | Regular |
Star-freeness is a syntactic property of expressions; aperiodicity is an algebraic property of a finite monoid. Schützenberger's theorem says they coincide, which converts a question about expression syntax into a decidable algebraic check. This is the deepest payoff of the algebraic view of automata.
Varieties of finite monoids
The Eilenberg correspondence is a bijection between varieties of regular languages and pseudovarieties of finite monoids — classes of finite monoids closed under submonoids, quotients and finite products.
Finiteness is not preserved by infinite products, so classes of finite algebras are not varieties in Birkhoff's sense. Pseudovarieties are the correct notion, and Reiterman's theorem gives them an equational characterisation using profinite identities rather than ordinary ones.
The Eilenberg correspondence (1976) and Reiterman's theorem (1982) postdate or coincide with the source text and are not developed there. Chapter III presents the automaton-as-algebra idea and Kleene's theorem; the classification programme is the direction that idea led.
Frequently asked questions
Is the syntactic monoid computable from an acceptor?
Yes. It is the transition monoid of the minimal acceptor — the monoid of functions on states induced by words — and it is computed by closing the letter maps under composition.
How large can the syntactic monoid be relative to the acceptor?
Exponentially larger. An n-state acceptor can have a syntactic monoid of size up to n^n, since the monoid consists of functions from states to states.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section III.4, book pages 124-128.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.