Aperiodic finite-state automaton

An aperiodic finite-state automaton (also called a counter-free automaton) is a finite-state automaton whose transition monoid is aperiodic.

Definition

A finite-state automaton is counter-free if the following property is true:

• as long as there is a loop in the automaton that can be taken with a word $u^m$ (i.e. word $u$ repeated $m$ times) for $m\ge 1$ from state $q$ to state $q$, then we also go from $q$ to $q$ by reading word $u$.Template:Page needed

Properties

A regular language 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 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^mz in L if and only if xyⁿ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, 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

• Template:Cite book
• Template:Cite thesis — An intensive examination of McNaughton, Papert (1971).
• Template:Cite book — Uses Green's relations to prove Schützenberger's and other theorems.

Template:Comp-sci-theory-stub