On the Representation of Finite Automata

2009/06/13 by Reis, Rogério, Moreira, Nelma, Almeida, Marco
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.0906.2477

Abstract

We give an unique string representation, up to isomorphism, for initially connected deterministic finite automata (ICDFAs) with n states over an alphabet of k symbols. We show how to generate all these strings for each n and k, and how its enumeration provides an alternative way to obtain the exact number of ICDFAs.

Related

• Aspects of enumeration and generation with a string automata representation
• Exact generation of acyclic deterministic finite automata
• From regular expressions to deterministic finite automata: 2^(n)/(2)+√(n)(log n)^Θ(1) states are necessary and sufficient
• Incremental construction of minimal acyclic finite-state automata
• Incremental Construction of Compact Acyclic NFAs