Re: Compress the finite state machine

>> The first step is, obviously, to minimize the number of states in the
>> DFA. You can find a method for this in Aho, Sethi and Ullman's
>> compiler book, though the version described there isn't particularly
>> efficient.


>Does anyone have a more efficient way to minimize the number of
>states in the DFA?


The method described in the abovementioned book uses in the worst case
quadratic time (even though it is elsewhere in the book claimed to be
O(n*log(n))). An O(n*log(n)) method can be found in Aho, Hopcroft and
Ullman's "The Design and Analysis of Computer Algorithms".


An improved version was published by Keller and Paige in
Communications of Pure and Applied Math., Vol 48, Num. 9-10, 1996. It
can also be found at http://cs.nyu.edu/cs/faculty/paige/research.html
(search for "minimum-state" within this page).


Torben Mogensen (torbenm@diku.dk)

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