I'm working on a NFA to DFA conversion tool that is different from the Subset Construction and I need to test this tool.

In order to be sure that the immplementation has no bug I'd like to generate a random NFA with these properties:

  • The NFA should be connected
  • The NFA should have one initial state and one or more final states
  • The NFA should have ε-moves

Is there a known algorithm or a paper that explains how to generate this NFA automaton as random as possible?

  • 3
    $\begingroup$ Related: What is a good algorithm for generating random DFAs? $\endgroup$ Sep 23, 2013 at 18:09
  • $\begingroup$ First, you have to fix the alphabet. But a real difficulty is to give a precise definition of "as random as possible". For instance, do you consider isomorphic NFA (obtained by permuting the states) as distinct ones? If you want a uniform distribution, which parameter do you consider: number of states, number of transitions? $\endgroup$
    – J.-E. Pin
    Sep 23, 2013 at 20:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.