Enumeration and Generation of Initially
Connected Deterministic
Finite Automata
### Marco Almeida, Nelma Moreira, and RogĂ©rio Reis

DCC-FC & LIACC, Universidade do Porto

E-mail: {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) initially-connected
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 pre-calculated 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..