
Technical Report: DCC200607
Enumeration and Generation of Initially
Connected Deterministic
Finite Automata
Marco Almeida, Nelma Moreira, and Rogério Reis
DCCFC & LIACC, Universidade do Porto
Email: {mfa,nam,rvr}@dcc.fc.up.pt
December 2006
Abstract
The representation of combinatorial objects is decisive for the
feasibility of several enumerative tasks. In this work, we present
a (unique) string representation for (complete) initiallyconnected
deterministic automata (ICDFA's) with n states over an alphabet
of k symbols. For these strings we give a regular expression and
show how they are adequate for exact and random generation,
allow an alternative way for enumeration and lead to an upper bound
for the number of ICDFA's. The exact generation algorithm can be
used to partition the set of ICDFA's in order to parallelize the
counting of minimal automata (and thus of regular languages). A
uniform random generator for ICDFA's is presented that uses a
table of precalculated values. Based on the same table, an optimal
coding for ICDFA's is obtained. We also establish an explicit
relationship between our method and the one used by Nicaud et al..
