Mirror Images and Schemes for the Maximal Complexity of Nondeterminism

Abstract

We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2ⁿ. The construction leads to cases, where the increase in complexity is maximal in the transition from nondeterministic devices to deterministic ones. We also discuss the crucial importance of the size of the alphabet and present some open problems.