[comp.theory] Possible number of NFAs to each DFA.

rdubey@eecs.wsu.edu (Rakesh Dubey - grad student) (03/09/91)

There is a problem regarding finite-state machines that I recently
came across and I would appreciate your thoughts on it.

Suppose we have a a description (Q, A, d, q, F) where Q is a set
of states, q is the start state, A is an alphabet and F is the set
of accepting state, finally d is a transition function. Now with
this data we can construct a finite number of DFAs and NFAs (say D
and N respectively). 

My question is: Is there some interesting mapping from the set N 
the set D? Can we say how many NFAs will in general correspond to
a given DFA?

-- 
Rakesh Dubey
rdubey@yoda.eecs.wsu.edu