Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!usc!sdd.hp.com!caen!dali.cs.montana.edu!milton!yoda.eecs.wsu.edu!rdubey
From: rdubey@eecs.wsu.edu (Rakesh Dubey - grad student)
Newsgroups: comp.theory
Subject: Clarification - Possible number of NFAs to each DFA.
Message-ID: <1991Mar09.004124.24269@eecs.wsu.edu>
Date: 9 Mar 91 00:41:24 GMT
References: <1991Mar08.192759.7668@eecs.wsu.edu>
Reply-To: rdubey@eecs.wsu.edu (Rakesh Dubey - grad student)
Organization: Washington State University, Pullman
Lines: 23


I am sorry about lack of clarity in a problem that I posted. The
correct (hopefully) version goes:

In the description (Q, A, d, q, F) , a set of states Q, an alphabet A
and a start state q are given. The only things that one can choose
are the transition function d and the accept states.

Now with this data we can construct a finite number of DFAs and NFAs 
(say D and N respectively).  (NFAs have lambda transitions).

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

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


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