finite state minimization proofs

"Ralph P. Boland" <>
20 Aug 2003 01:34:23 -0400

          From comp.compilers

Related articles
Announcing PyGgy (Tim Newsham) (2003-08-15)
finite state minimization proofs (Ralph P. Boland) (2003-08-20)
Re: finite state minimization proofs (Derk Gwen) (2003-08-23)
| List of all articles for this month |

From: "Ralph P. Boland" <>
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.



Post a followup to this message

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