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