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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Related: What is a good algorithm for generating random DFAs? $\endgroup$
    – Gilles 'SO- stop being evil'
    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

0

Reset to default

Your Answer

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