On 10/26/07, Stewart Stremler <[EMAIL PROTECTED]> wrote: > begin quoting Christopher Smith as of Thu, Oct 25, 2007 at 10:26:45PM -0700: > > Stewart Stremler wrote: > [snip] > > > I don't know if there's a lightbulb-moment or not. I think they're > > > pretty simple -- the hard stuff is in the proofs and the transforms. > > > > > And the nice thing about a functional language (or at least *some* > > functional languages), is that the language does that "hard stuff" for > > you. > > I completely fail to see how *any* programming language could prove > that an NDFA and a DFA are equivalent. Or show why a transforms is > guaranteed to work.
In the PlanetMath article on NDFAs the following claim is made. <claim> Any regular grammar can be represented by an NDFA. Any string accepted by the NDFA is in the language represented by that NDFA. Furthermore, it is a straight-forward process to generate an NDFA for any regular grammar. Actual operation of an NDFA is generally intractable, but there is a simple process to transform any NDFA into a DFA, the operation of which is very tractable. Regular expression matchers tend to operate in this manner. </claim> http://planetmath.org/encyclopedia/NonDeterministicFiniteAutomaton.html So I would suggest that the problem can at least be reduced to proving that two DFAs are equivalent. BobLQ -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
