From owner-freebsd-hackers  Wed Feb  5 17:51:48 1997
Return-Path: <owner-hackers>
Received: (from root@localhost)
          by freefall.freebsd.org (8.8.5/8.8.5) id RAA03979
          for hackers-outgoing; Wed, 5 Feb 1997 17:51:48 -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 RAA03941
          for <freebsd-hackers@freebsd.org>; Wed, 5 Feb 1997 17:50:53 -0800 (PST)
Received: by dg-rtp.dg.com (5.4R3.10/dg-rtp-v02)
	id AA20758; Wed, 5 Feb 1997 20:50:14 -0500
Received: from ponds by dg-rtp.dg.com.rtp.dg.com; Wed,  5 Feb 1997 20: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 UAA28238; Wed, 5 Feb 1997 20:20:04 -0500 (EST)
Received: (from rivers@localhost) by lakes.water.net (8.8.3/8.6.9) id UAA25717; Wed, 5 Feb 1997 20:24:34 -0500 (EST)
Date: Wed, 5 Feb 1997 20:24:34 -0500 (EST)
From: Thomas David Rivers <ponds!rivers@dg-rtp.dg.com>
Message-Id: <199702060124.UAA25717@lakes.water.net>
To: ponds!lakes.water.net!rivers, ponds!lambert.org!terry
Subject: Re: [Fwd: freebsd performance.]
Cc: ponds!freebsd.org!freebsd-hackers, ponds!xinside.com!patrick
Content-Type: text
Sender: owner-hackers@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

> > > There are two different 'engines' - NFA (nondeterministic finite
> > > automaton) and DFA (deterministic finite automaton).  Perl is
> > > 'traditional NFA' according to Mr. Friedl, while POSIX leans towards
> > > DFA-like behavior in all cases (always returns 'leftmost-longest' that
> > > matches - perl returns I believe the first part that matches).
> >  
> >  Ah, but you should remember that all NFAs are convertable to DFAs.
> 
> What?  What?  You've solved the "machine translation of natural
> languages" problem?!?!  Why wasn't I told?!?!
> 
> 
> 					Terry Lambert
> 					terry@lambert.org

 Nope - elementary automata theory - NFAs are convertable to DFAs (in fact,
it's on page 17 of Hopcroft and Ullman's "Introduction to Automata Theory,
Languages, and Computation" - one of the very elementary ideas.)

 The key to remember here is the FA part (Finite Automata) - they are just
regular languages.  Regular languages are regular languages; rather DFA or
NFA.

 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.

 Unfortunately, this has very little to do with natural languages.

 For a thorough understanding of automata theory and computation theory;
I would recommend that Hopcroft and Ullman text, published by Addison Wesley.
[I'm not sure it's still in print, however.]  Unfortunately, most
compiler courses in Universities these days no longer bother with
automata theory...

	 - Dave Rivers -