Classification of prime deterministic automata over finite alphabets
Prime Accessible Deterministic Automata
Formal Languages and Automata Theory
Summary
This paper identifies which simple types of deterministic state machines, called automata, are 'prime'—meaning they cannot be broken down further. The authors show that all single-state machines are prime and that over a single-letter alphabet, prime automata correspond to cycles with lengths based on prime powers or simple chains. They confirm that more complicated machines with two or more letters are not prime. They also analyze the structure of infinite automata built from all finite input words and offer a precise condition when certain combinations of these automata are isomorphic.
What this means in practice
- •For automata theorists: Provides a complete classification of prime automata shapes that helps understand when complex deterministic automata can be decomposed.
- •For formal language tool developers: Clarifies limits on minimal components in automata used for language recognition and transformations involving unary alphabets.
A theory result. No direct application yet.
Authors
Shen Zhao, Chenghe Xu
Abstract
We classify prime accessible deterministic automata over finite alphabets, both among finite automata and among automata with arbitrary state sets. Every one-state automaton is prime. Over a one-letter alphabet, a finite nontrivial automaton is prime exactly when it is a cycle of prime-power length or a finite chain ending in a fixed state. The unique infinite accessible unary automaton, up to isomorphism, is also prime. Every nontrivial automaton over an alphabet with at least two letters is not prime. Shen proved the finite case; we give a shorter proof. We also characterize a decomposition of the automaton whose states are all finite input words. The reachable product of the quotients by the least right congruences identifying the empty word with nonempty words $p$ and $q$, respectively, is isomorphic to this automaton exactly when $p^r\ne q^s$ for all positive integers $r,s$.