Random Generation Models for NFAs

The aim of this study is the random generation of non-deterministic automata. We focus our attention on the random generation processed with bitstreams for which we present a probabilistic analysis. Let m be the size of the alphabet. We show that the DFAs obtained by subset construction from n-state NFAs based on equiprobable bitstreams have a probability of being of size m + 2 that tends to 1 when n tends to infinity. This property gives an asymptotical explanation to van Zijl's experimental results concerning the succinctness of NFAs. We also determine the probability that a state is reachable from an equiprobably chosen DFA state. We show that the distribution of the subsets that appear during the subset construction is an equiprobable one in the case of bitstreams generated with the probability 2 - 2n-1/n. This result is related to the conjecture of Leslie, Raymond and Wood, which says that the number of states of the DFA is maximum when the density of the NFA is approximately equal to 2/n. Finally we extend this probabilistic study to the case of *-NFAs defined by van Zijl.