3
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Related: What is a good algorithm for generating random DFAs? $\endgroup$ – Gilles 'SO- stop being evil' Sep 23 '13 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 '13 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.