An aperiodic finite-state 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 celebrated result of algebraic automata theory is due to Marcel-Paul Schützenberger.[1]
An aperiodic automaton satisfies the Cerny conjecture.[2]
References
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
