Multiple-entry finite automata

摘要

A multiple-entry finite automaton (mefa) is a finite automaton where any state can serve as an initial state. The reason for studying such automata is that there is a class of regular sets which can be recognized much more economically with a parallel bank of identical mefa's than with conventional finite automata. In this paper we study properties of mefa's and formulate a necessary and sufficient condition for regular sets to be mefa-recognizable. We also develop algorithms for testing for this condition and for constructing the recognizing mefa whenever this conditions is satisfied.