Technical Report: DCC-2007-05

Exact Generation of Minimal Acyclic Deterministic Finite Automata

Marco Almeida, Nelma Moreira and Rogério Reis

DCC-FC & LIACC, Universidade do Porto
R. 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

June 2007

Abstract

We 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.