MINIMALIZATIONS OF NFA USING THE UNIVERSAL AUTOMATON

Abstract

As is well known, each minimal NFA for a regular language L is isomorphic to a subautomaton of the so-called universal automaton [Formula: see text] for L. We explore and compare various conditions on sets of states of [Formula: see text] which are related to the fact that induced subautomata of [Formula: see text] accept the whole language L. The methods of several previous works on minimalizations of NFA can be modified so that they fit in our approach. We also propose a new algorithm which is easy to implement.