Английская Википедия: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.
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.[1] 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 which 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 xymz in L if and only if xynz in L. Another way to state Schützenberger's theorem is that star-free languages and counter-free languages are the same thing.Шаблон:Explain
An aperiodic automaton satisfies the Černý conjecture.[2]
References
- Шаблон:Cite book
- Шаблон:Cite thesis — An intensive examination of McNaughton, Papert (1971).
- Шаблон:Cite book — Uses Green's relations to prove Schützenberger's and other theorems.
Шаблон:Formal languages and grammars
