Re: Compress the finite state machine

Chris F Clark <cfc@world.std.com> 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
ISBN 0-13-542258-2).


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
                Machine Complexity
  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
                Machine Containment
  4.7 Machine Histories and Finite Memory




Best wishes,
Steve
--
  Steven Hand sassth@unx.sas.com

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