finite state minimization proofs

"Ralph P. Boland" <rpboland@math.uwaterloo.ca>
20 Aug 2003 01:34:23 -0400

          From comp.compilers
Related articles
Announcing PyGgy newsham@lava.net (Tim Newsham) (2003-08-15)
finite state minimization proofs rpboland@math.uwaterloo.ca (Ralph P. Boland) (2003-08-20)
Re: finite state minimization proofs derkgwen@HotPOP.com (Derk Gwen) (2003-08-23)
| List of all articles for this month |
From: "Ralph P. Boland" <rpboland@math.uwaterloo.ca>
Newsgroups: comp.compilers
Date: 20 Aug 2003 01:34:23 -0400
Organization: University of Waterloo
References: 03-08-053
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.




Thanks


Ralph

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.