Exact generation of acyclic deterministic finite automata
Marco Almeida, Nelma Moreira, Rogério Reis · arXiv (Cornell University) · 2009
We give a canonical representation for trim acyclic deterministic finite automata (Adfa) with n states over an alphabet of k symbols. Using this normal form, we present a backtracking algorithm for the exact generation of Adfas. This algorithm is a non trivial adaptation of the algorithm for the exact generation of minimal acyclic deterministic finite automata, presented by Almeida et al.