From owner-freebsd-hackers  Wed Feb  5 20:50:41 1997
Return-Path: <owner-hackers>
Received: (from root@localhost)
          by freefall.freebsd.org (8.8.5/8.8.5) id UAA06444
          for hackers-outgoing; Wed, 5 Feb 1997 20:50:41 -0800 (PST)
Received: from dg-rtp.dg.com (dg-rtp.rtp.dg.com [128.222.1.2])
          by freefall.freebsd.org (8.8.5/8.8.5) with SMTP id UAA06424
          for <freebsd-hackers@freefall.FreeBSD.org>; Wed, 5 Feb 1997 20:50:38 -0800 (PST)
Received: by dg-rtp.dg.com (5.4R3.10/dg-rtp-v02)
	id AA29768; Wed, 5 Feb 1997 23:50:07 -0500
Received: from ponds by dg-rtp.dg.com.rtp.dg.com; Wed,  5 Feb 1997 23:50 EST
Received: from lakes.water.net (lakes [10.0.0.3]) by ponds.water.net (8.8.3/8.7.3) with ESMTP id XAA01887; Wed, 5 Feb 1997 23:31:22 -0500 (EST)
Received: (from rivers@localhost) by lakes.water.net (8.8.3/8.6.9) id XAA26215; Wed, 5 Feb 1997 23:35:54 -0500 (EST)
Date: Wed, 5 Feb 1997 23:35:54 -0500 (EST)
From: Thomas David Rivers <ponds!rivers@dg-rtp.dg.com>
Message-Id: <199702060435.XAA26215@lakes.water.net>
To: ponds!freefall.cdrom.com!freebsd-hackers, ponds!xinside.com!patrick,
        ponds!lambert.org!terry
Subject: Re: [Fwd: freebsd performance.]
Content-Type: text
Sender: owner-hackers@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

> 
> >  The basic idea for the equivalence proof is that:
> > 	
> > 	1) All DFAs are NFAs (of course)
> > 	2) Any NFA can be represented as a DFA where the states of
> > 	    the DFA tuples of the states of the NFA.  [Think about
> > 	    how you would write an NFA simulator; you'd have N
> > 	    possible states moving from transition to transition.]
> > 
> >  So, DFA <-> NFA.
> 
> Cheater... "non-finite" != "infinite" in this definition.
> 
> BTW: The "machine translation of natural languages" question was asked
> tongue-in-cheek... I suppose I need to add "8-)"'s.  8-(.
> 
> 
> 					Terry Lambert

 Err, umm,  in the context of regular expressions; (recall the original
discussion was the speed of regex vs. pearl):

   NFA is
      Non-deterministic _Finite_ Automata
   DFA is
      Deterministic _Finite_ Automata

 Determinism is quite a different idea from finite/infinite.

 We haven't crossed over into the "infinite" yet :-)  It's rather
interesting to banty around the idea infinite automata, and possible 
ramifications on a G.O.D. (General Omniscient Device), much less our
own existence; especially over some beer :-)

	- Dave Rivers -