22 Mar 1999 01:15:13 -0500

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) |

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.