Algebraic Automata Theory #1

02 Sep, 2026

Most intro courses to automata theory only cover the classical theory of authomata: DFAs, NFAs, regular expressions, their properties, and the conversions between them. But some important results in automata theory cannot be proved using only those methods. Sometimes we need to reach to the scary algebraic structures of semigroups and monoids.

Algebraic Automata Theory studies the (perhaps surprising) connection between automata and algebra. This series of posts are my personal notes as I try to learn AAT. I'm sure they contain many errors, but I hope that they are usefull to someone trying to learn it too.

Semigroups

Since we want to study the connection between algebra and automata, we need to start with some algebrai concepts.

Def: A semigroup is a pair $S = (S, \cdot)$ where $S$ is a set and $\cdot : S \times S \to S$ is an associative binary operation on $S$ , that is: $ a \cdot (b \cdot c) = (a \cdot b) \cdot c \qquad \forall a,b,c \in S$

Since the semigroup operation (often called "multiplication") is associative, we don't need to worry about parenthesis since the evaluation of expressions becomes unambiguous. It is common to use the notation $a^{n}$ to denote the multiplication of $n \in N$ copies of $a \in S$ .

Lemma: The following properties hold:

$a^{n} a^{m} = a^{n + m}$

$(a^{n})^{m} = a^{n m}$

There are some important kinds of semigroup elements with certain properties:

Left identities: $1_{l} \cdot a = a (\forall a \in S)$
Right identities: $a \cdot 1_{r} = a (\forall a \in S)$
Left zeroes: $0_{l} \cdot a = 0_{l} (\forall a \in S)$
Right zeroes: $a \cdot 0_{r} = 0_{r} (\forall a \in S)$
Identities: $1 \cdot a = a = a \cdot 1 (\forall a \in S)$
Zeroes: $0 \cdot a = 0 = a \cdot 0 (\forall a \in S)$

Lemma: A semigroup can have, at most, one identity and one zero element.

Proof: Let $a, b$ be two identity elements. Then $a = a b = b$ . The same argument applies to the other case.

A semigroup with identity is called a monoid (which are also important for automata theory):

Def: A monoid is a triple $M = (M, \cdot, 1)$ where $M$ is a set, $\cdot : M \times M \to M$ is an associative binary operation on $M$ , and $1 \in M$ is an identity element, that is: $ a \cdot (b \cdot c) = (a \cdot b) \cdot c \qquad \forall a,b,c \in M$ $ a \cdot 1 = a = 1 \cdot a \qquad \forall a \in M$

Any semigroup $S$ can be turned into a monoid $S^{1}$ :

S^{1} = {\begin{matrix} S & if S has an identity element \\ S \cup {1} & otherwise \end{matrix}

where $1 \notin S$ is the identity of the monoid and the multiplication is extended accordingly.

There are other important kinds of semigroups:

Finite Semigroups: the carrier set is finite
Abelian Semigroups: the multiplication is commutative
Groups: All elements have inverses

Another important kind of element of a semigroup are the idempotents. An element $i \in S$ is said to be idempotent if $i^{2} = i$ . The set of idempotent elements of $S$ is denoted by $E (S)$ .

Thm: Every finite semigroup has an idempotent element.

Proof: Let $a \in S$ . Since $S$ is finite, the sequence $a, a^{2}, a^{3}, \dots$ must eventually become periodic with period $p$ . Let $k$ be the first integer such that $a^{k} = a^{k + p}$ . Let $m = k p$ . Since $m > k$ , $a^{m} = a^{m + k p} = a^{m + m} = a^{2 m} = (a^{m})^{2}$ . Thus, $a^{m}$ is an idempotent element.

Homomorphisms

Perhaps the most important feature of modern mathematics is the study of not only structures, but also of the structure preserving maps between them:

Def: Let $S = (S, \cdot)$ and $T = (T, \times)$ be semigroups. A semigroup homomorphism is a function $φ : S \to T$ such that $φ (a \cdot b) = φ (a) \times φ (b)$

This notion extends easily to monoids by requiring that the identity element is also preserved, i.e., $φ (1_{S}) = 1_{T}$ .