Theory of Adaptive Mechanisms. Part Iv. Deterministic Realization and Simulation of Nondeterministic Automata

摘要

The report investigates the deterministic realization of nondeterministic finite automata through the subset construction. It had been speculated by Rabin that the exponential increase in the number of states in this construction could be improved. Contrary to this a class of nondeterministic automata is constructed by the author for which the subset construction yields a reduced, connected deterministic automata with exactly 2 to the n power states. (Author)