Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!samsung!uakari.primate.wisc.edu!dali.cs.montana.edu!milton!yoda.eecs.wsu.edu!rdubey
From: rdubey@eecs.wsu.edu (Rakesh Dubey - grad student)
Newsgroups: comp.theory
Subject: Possible number of NFAs to each DFA.
Message-ID: <1991Mar08.192759.7668@eecs.wsu.edu>
Date: 8 Mar 91 19:27:59 GMT
Reply-To: rdubey@eecs.wsu.edu (Rakesh Dubey)
Organization: Washington State University, Pullman
Lines: 16

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