Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!decwrl!ucbvax!agate!eos!ames!mailrus!tut.cis.ohio-state.edu!osu-cis!att!chinet!mcdchg!nud!sunburn!gtx!al
From: al@gtx.com (Alan Filipski)
Newsgroups: comp.misc
Subject: Re: Nondeterminism vs. Determinis
Message-ID: <719@gtx.com>
Date: 26 Aug 88 22:38:40 GMT
References: <36400004@hcx2>
Reply-To: al@gtx.UUCP (Alan Filipski)
Organization: GTX Corporation, Phoenix
Lines: 21

->Greg, lee@uhccux.uhcc.hawaii.edu claimed any NFSA can be simulated by 
->a DFSA (NFSA = Non-deterministic Finite State Automaton).  Not so!
->The simulation is 'try all paths with backtracking'  However, in the
->most general case, some of the false paths may not terminate.  Therefore,
->the NFSA, which magically avoids the wrong answers (that's why it's
->non-deterministic) is more powerful.  QED.

QED nothing.  of course you can write a stupid simulator that gets
caught in infinite loops.  Try a breadth-first simulation instead of
depth-first. This is basically equivalent to the usual construction
that maps each subset of the NDFSA with a single state of the new
DFSA.

>Henry Troup
->Bell Northern Research does not make non-deterministic machines.


  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 ( Alan Filipski, GTX Corp, 8836 N. 23rd Avenue, Phoenix, Arizona 85021, USA )
 ( {allegra,decvax,hplabs,amdahl,nsc}!sun!sunburn!gtx!al       (602)870-1696 )
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~