|
|
||||||||
|
|||||||||
|
Technical Report: DCC-2007-05Exact Generation of Minimal Acyclic Deterministic Finite AutomataMarco Almeida, Nelma Moreira and Rogério ReisDCC-FC & LIACC, Universidade do PortoR. do Campo Alegre 1021/1055 , 4169-007 Porto, Portugal Phone: +351 220402926 , Fax: 351 22 402 950 E-mail: {mfa, nam,rvr}@ncc.up.pt AbstractWe give a canonical representation for minimal acyclic deterministic finite automata (MADFA) with n states over an alphabet of k symbols. Using this normal form, we present a method for the exact 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. |
||||||||
|