---
tag: 3WDZY1J002
kind: concept
name: Krohn–Rhodes theory
msc: [20M35, 68Q70]
sources:
  - url: https://en.wikipedia.org/wiki/Krohn–Rhodes_theory
same_as:
  wikidata: Q6438788
  wikipedia: Krohn–Rhodes theory
---

## Summary

Krohn–Rhodes theory studies finite [[semigroups|0XMEM406JM]] and finite automata by decomposing them into simple building blocks.
Its central result is the Krohn–Rhodes theorem.
It says that every finite semigroup divides an iterated [[wreath product|W1X984PKJ9]] of finite [[simple groups|0YMYMNQ0QZ]] and copies of the flip-flop, a monoid of resets.
The simple groups in such a decomposition can be chosen among the simple groups that divide the semigroup.
So every finite automaton can be built in a cascade from reversible parts, which are groups, and memory parts, which are flip-flops.
The least number of group levels needed is the complexity of the semigroup, a central object of study in the theory.

## Explanations

### L1 human

A finite automaton is a machine with finitely many states that reads input one symbol at a time.
Krohn–Rhodes theory says that any such machine can be simulated by a chain of very simple machines, each feeding its state to the next ones.
The simple machines are of two kinds: those that permute their states reversibly, like the hands of a clock, and one-bit memories that can be set or reset.
This is a kind of prime factorization for machines.