Descriptional Complexity of Deterministic Finite Automata with Multiple Initial States
Martin Kappes · Scientific Publication Server (Frankfurt University of Applied Sciences) · 2000
We study the descriptional complexity of finite automata with multiple initial states and a deterministic transition function. The model is compared to ordinary deterministic and nondeterministic finite automata. It allows to use nondeterminism in practical applications and still provides in some cases exponential savings in the number of states compared to the smallest deterministic finite automaton. Using another acceptance criterion, even exponential savings over nondeterministic finite automata are achievable while the implementation remains easy.