Exact Generation of Minimal Acyclic Deterministic
Marco Almeida, Nelma Moreira · 2007
We give a canonical representation for minimal acyclic de- terministic finite automata (MADFA) with n states over an alphabet of k symbols. Using this normal form, we present a method for the ex- act generation of MADFAs. This method avoids a rejection phase, that would be needed if a generation algorithm for a larger class of objects that contains the MADFAs were used. We give an upper bound for MADFAs enumeration that is exact for small values of n.