An aperiodic finite-state automaton (also called a counter-free automaton) is a

finite-state automaton A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

whose transition monoid is aperiodic.

Properties

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

is star-free if and only if it is accepted by an automaton with a finite and aperiodic transition monoid. This result of algebraic

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to cognitive science and mathematical l ...

is due to Marcel-Paul Schützenberger. In particular, the minimum automaton of a star-free language is always counter-free (however, a star-free language may also be recognized by other automata that are not aperiodic). A counter-free language is a regular language for which there is an integer ''n'' such that for all words ''x'', ''y'', ''z'' and integers ''m'' ≥ ''n'' we have ''xy''^''m''''z'' in ''L'' if and only if ''xy''^''n''''z'' in ''L''. For these languages, when a string contains enough repetitions of any substring (at least ''n'' repetitions), changing the number of repetitions to another number that is at least ''n'' cannot change membership in the language. (This is automatically true when ''y'' is the

empty string In formal language theory, the empty string, or empty word, is the unique String (computer science), string of length zero. Formal theory Formally, a string is a finite, ordered sequence of character (symbol), characters such as letters, digits ...

, but becomes a nontrivial condition when ''y'' is non-empty.) Another way to state Schützenberger's theorem is that star-free languages and counter-free languages are the same thing. An aperiodic automaton satisfies the Černý conjecture.

References

* * — An intensive examination of McNaughton, Papert (1971). * — Uses

Green's relations In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. ...

to prove Schützenberger's and other theorems. Finite-state machines {{comp-sci-theory-stub