Stewart Stremler 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. > Hmm... I can't think of how one might do the NDFA/DFA proof, but certainly your typical Haskell or ML compiler can verify the equivalence of a transform. >> Of course, things like the halting problem aren't solvable (which >> really begs the question of just how easy state machines are), but the >> stuff that can be solved can be solved for you by the computer. >> > > Huh? > > How does the halting problem have anything to do with the utility of > state machines? > One thing that is perhaps useful to be able to solve about an automaton might be whether it ever halts for a finite set of input. This is useful as it can inform any number of other conclusions about the code. Unfortunately, you can't have a generalized algorithm which can determine this accurately for all cases.
--Chris -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
