Re: Compress the finite state machine

Steven Hand <sassth@unx.sas.com>
22 Mar 1999 01:15:13 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: Compress the finite state machine torbenm@diku.dk (Torben Mogensen) (1999-03-04)
Re: Compress the finite state machine jes6@eecs.lehigh.edu (James E. Stine) (1999-03-04)
Re: Compress the finite state machine allanmac@blueprint.com (Allan MacKinnon) (1999-03-04)
Re: Compress the finite state machine hunk@alpha1.csd.uwm.edu (1999-03-04)
Re: Compress the finite state machine stans@lucent.com (Sicco Tans) (1999-03-10)
Re: Compress the finite state machine torbenm@diku.dk (Torben Mogensen) (1999-03-22)
Re: Compress the finite state machine sassth@unx.sas.com (Steven Hand) (1999-03-22)
| List of all articles for this month |

From: Steven Hand <sassth@unx.sas.com>
Newsgroups: comp.compilers
Date: 22 Mar 1999 01:15:13 -0500
Organization: Compilers Central
References: 99-03-014
Keywords: books

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


Post a followup to this message

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