|[2 earlier articles]|
|Re: Compress the finite state machine firstname.lastname@example.org (Torben Mogensen) (1999-03-04)|
|Re: Compress the finite state machine email@example.com (James E. Stine) (1999-03-04)|
|Re: Compress the finite state machine firstname.lastname@example.org (Allan MacKinnon) (1999-03-04)|
|Re: Compress the finite state machine email@example.com (1999-03-04)|
|Re: Compress the finite state machine firstname.lastname@example.org (Sicco Tans) (1999-03-10)|
|Re: Compress the finite state machine email@example.com (Torben Mogensen) (1999-03-22)|
|Re: Compress the finite state machine firstname.lastname@example.org (Steven Hand) (1999-03-22)|
|From:||Steven Hand <email@example.com>|
|Date:||22 Mar 1999 01:15:13 -0500|
Chris F Clark <firstname.lastname@example.org> writes:
> Felix Mish wrote:
> > I am evaluating the ways to compress the finite state machine.
> > Is there anyone be kind enough to provide some possible solutions?
> If you mean to "optimize the finite state machine so that it has fewer
> states", I don't have any recommendations. I vaguely recall that
> there might be an algorithm in the dragon book that works by creating
> equivalence classes.
A good textbook that covers this is "Machines, Languages, and Computation"
by Peter J. Denning, Jack B. Dennis, and Joseph E. Qualitz (1978 Prentice-Hall
Here are the sections under Chapter 4 "Finite State Machines":
4.1 Properties of Finite-State Machines
Machines with Transition-Assigned Output
Machines with State-Assigned Output
4.2 State Sequences
4.3 Conversion Between Transition and State-Assigned Machines
4.4 Equivalence of Finite-State Machines
4.5 Equivalent States
4.6 State Reduction and Equivalence Testing
Reduced, Connected Machines
Distinguishing Sequences and k-Equivalence
Partitioning the State Set
Construction of Reduced Machines <<<note
Isomorphism of Equivalence
4.7 Machine Histories and Finite Memory
Steven Hand email@example.com
Return to the
Search the comp.compilers archives again.