Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs
Abstract
We define the class of forward injective finite automata (FIFA) and study some of their properties. Each FIFA has a unique canonical representation up to isomorphism. Using this representation an enumeration is given and an efficient uniform random generator is presented. We provide a conversion algorithm from a nondeterministic finite automaton or regular expression into an equivalent FIFA. Finally, we present some experimental results comparing the size of FIFA with other automata.
Domains
Computer Science [cs]Origin | Files produced by the author(s) |
---|
Loading...