|Announcing PyGgy email@example.com (Tim Newsham) (2003-08-15)|
|finite state minimization proofs firstname.lastname@example.org (Ralph P. Boland) (2003-08-20)|
|Re: finite state minimization proofs derkgwen@HotPOP.com (Derk Gwen) (2003-08-23)|
|From:||"Ralph P. Boland" <email@example.com>|
|Date:||20 Aug 2003 01:34:23 -0400|
|Organization:||University of Waterloo|
|Keywords:||DFA, theory, question|
|Posted-Date:||20 Aug 2003 01:34:22 EDT|
Where can I find the simplest proofs that
the algorithms for finite state machine minimiztion
are correct; i.e. that the machine constructed has
the fewest number of states?
I am looking for a proof for the algorithm that is
O(n\log n) for an n state input.
I would also be interested in a proof for the O(n^2) algorithm.
Are there publicly available standard implementations
of these algorithms and the algorithm for constructing
a FSM from a regular expression if so where?
Are there implementations of these algorithms or variations of
them that are particularly fast and if so where?
I am designing an algorithm for constructing a minimum
state FSM directly from a regular expression and I
will want to compare my algorithms and proofs with
the competing proofs/algorithms.
Return to the
Search the comp.compilers archives again.