Date: Wed, 5 Feb 1997 20:24:34 -0500 (EST) From: Thomas David Rivers <ponds!rivers@dg-rtp.dg.com> To: ponds!lakes.water.net!rivers, ponds!lambert.org!terry Cc: ponds!freebsd.org!freebsd-hackers, ponds!xinside.com!patrick Subject: Re: [Fwd: freebsd performance.] Message-ID: <199702060124.UAA25717@lakes.water.net>
next in thread | raw e-mail | index | archive | help
> > > 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 -
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199702060124.UAA25717>