On Measuring Nondeterminism in Regular Languages

1. Introduction: Nondeterminism plays a profound role in the theory of automata. For certain types of automata, such as pushdown automata, it enhances their power. For other automata, such as Turing machines and finite automata, nondeterminism does not enhance computational power but may increase efficiency. For Turing machines, the investigation of whether nondeterminism actually can result in savings of resources such as time or space leads to very difficult open problems, such as the P vs. NP and LBA problems. The present paper investigates the role of nondeterminism at the other end of the hierarchy of automata.