Combinatorial and Automata Applications
Finite State Acceptors and Recognisable Languages
A finite acceptor is a unary algebra with a distinguished subset. Once phrased that way, the pumping lemma and the closure properties are algebraic facts about finite index.
- Present a finite acceptor as an algebra of unary operations.
- Define recognisability and the language accepted by an acceptor.
- Construct the Myhill–Nerode right congruence and state its index characterisation.
- Derive the minimal automaton as a quotient algebra.
- Prove closure under Boolean operations using products.
- Explain the pumping lemma as a pigeonhole argument on states.
01An acceptor is a unary algebra
A deterministic finite acceptor over an alphabet Σ consists of a finite state set Q, a transition function for each letter, an initial state and a set of accepting states.
The algebra proper is the unary structure; the initial state and accepting set turn it into a language-recognising device. Separating the two is what makes the algebraic arguments clean: the transition structure is an algebra of type (1, 1, …, 1), and everything about it is inherited from the general theory of unary algebras.
Algebras with only unary operations have distributive subuniverse lattices, and their subuniverses are the sets closed under all transitions. Generation reduces to orbit closure. This tractability is why automata theory yields clean results where general algebra does not.
02Words, the free monoid and the extended transition
The set Σ* of words over Σ is the free monoid on Σ. The transition function extends from letters to words by composition, and this extension is exactly the universal property of the free monoid applied to the transformation monoid of Q.
- Letters give unary mapsEach a ∈ Σ gives δ_a : Q → Q, an element of the monoid of all transformations of Q.
- The free monoid maps inBy freeness, the assignment a ↦ δ_a extends uniquely to a monoid homomorphism Σ* → T(Q), the transformation monoid.
- Words act on statesδ_w for a word w is the composite of the letter maps. The empty word gives the identity.
- Acceptancew is accepted when δ_w applied to the initial state lands in the accepting set. The language accepted is the set of all such w.
A language is recognisable when it is the language accepted by some finite acceptor. The image of Σ* in T(Q) is a finite monoid, and that monoid — the transition monoid — carries all the information, a point developed on the next page.
03The Myhill–Nerode congruence
Given a language L ⊆ Σ*, define a right congruence on Σ* by declaring two words equivalent when no suffix distinguishes them.
A language L is recognisable if and only if ≡L has finite index — finitely many equivalence classes. Moreover the number of classes equals the number of states of the minimal acceptor for L.
The theorem converts a question about the existence of a machine into a question about the index of an explicitly defined equivalence relation. That is a genuine reduction: index is computable for many languages where guessing an acceptor is not.
04The minimal automaton as a quotient
- input: recognisable language L ⊆ Σ*
- form the quotient Σ*/≡_L — finitely many classes by Myhill–Nerode
- states := the classes; initial state := the class of the empty word
- transition: δ_a([u]) := [ua] (well defined since ≡_L is a right congruence)
- accepting states := { [u] : u ∈ L } (well defined by taking w empty)
- the result accepts exactly L and has the fewest possible states
- equivalently: minimise any acceptor by quotienting by state indistinguishability
Read algebraically, minimisation is the first isomorphism theorem. The acceptor maps onto its quotient by the indistinguishability congruence, and the quotient is minimal because the congruence is the largest one compatible with the accepting set.
05Closure properties from products
Recognisable languages are closed under the Boolean operations, and the proofs are direct product constructions.
| Operation | Construction | State count |
|---|---|---|
| Complement | swap accepting and non-accepting states | unchanged |
| Intersection | product acceptor, accept when both accept | product of state counts |
| Union | product acceptor, accept when either accepts | product of state counts |
| Concatenation | nondeterministic construction, then determinise | may be exponential |
| Kleene star | nondeterministic construction, then determinise | may be exponential |
| Reversal | reverse transitions, then determinise | may be exponential |
The Boolean cases are algebraically trivial: the product acceptor is the direct product of the two unary algebras, and the accepting set is chosen appropriately in the product. Complementation needs the acceptor to be deterministic and complete, which is why nondeterministic acceptors do not close under complement so easily.
06The pumping lemma as pigeonhole
Any sufficiently long accepted word must revisit a state, and the segment between the two visits can be repeated arbitrarily.
- input: acceptor with n states; accepted word w with |w| ≥ n
- the run on w visits |w| + 1 states, so by pigeonhole two coincide
- write w = xyz where the repeated state occurs after x and after xy, y ≠ ε
- then δ_y fixes that state, so it may be traversed any number of times
- therefore xy^k z is accepted for every k ≥ 0
- contrapositive: if some xy^k z fails, the language is not recognisable
Algebraically this says that the transition monoid is finite, so the powers of any element are eventually periodic. Finiteness of the monoid is the whole content, and every pumping-style argument is a restatement of it.
Frequently asked
Are nondeterministic acceptors more powerful?
No — the subset construction converts any nondeterministic acceptor into a deterministic one accepting the same language, at a possible exponential cost in states. The class of recognisable languages is unchanged, which is why the algebraic characterisation via finite index is insensitive to determinism.
Is the minimal acceptor unique?
Yes, up to isomorphism, provided unreachable states are discarded. This is unusual: most minimisation problems in algebra have no canonical answer. The uniqueness comes from ≡L being the largest right congruence saturating L, so the quotient is canonically determined by the language.
Why treat automata algebraically at all?
Because it makes the results theorems about finite algebras rather than facts about machines, which connects them to the rest of the subject. The Kleene and Schützenberger characterisations on the next page are statements about monoid varieties, and they were found by taking the algebraic view seriously.
- 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.