The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.7.7 Finite State Machine Minimization

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A deterministic finite automata M.

Problem: The smallest deterministic finite automata M' such that M' behaves identically to M'

Excerpt from The Algorithm Design Manual: Problems associated with constructing and minimizing finite state machines arise repeatedly in software and hardware design applications. Finite state machines are best thought of as pattern recognizers, and minimum-size machines correspond to recognizers that require less time and space. %Space is usually the more important issue. Complicated control systems and compilers are often built using finite state machines to encode the current state and associated actions, as well as the set of possible transitions to other states. Minimizing the size of this machine minimizes its cost.

Finite state machines are best thought of as edge-labeled directed graphs, where each vertex represents one of n states and each edge a transition from one state to the other on receipt of the alphabet symbol that labels the edge. The automaton above analyzes a given sequence of coin tosses, with the dark states signifying that an even number of heads have been observed.


Implementations

  • Grail: finite automata and regular expressions (C++) (rating 9)
  • AT&T FSM Library – Finite-State Machine Library (Binary) (rating 9)
  • Fire-Engine and Spare-Parts String and Language Algorithms (C++,C) (rating 8)
  • JFLAP: Formal Languages and Automata Theory (Java) (rating 7)
  • Handbook of Algorithms and Data Structures (C,Pascal) (rating 5)
  • Java Compatible Toolkit (Java) (rating 3)

  • Recommended Books

    Practical Algorithms for Programmers by A. Binstock and J. Rex Handbook of Algorithms and Data Structures by G. Gonnet and R. Baeza-Yates The Design and Analysis of Computer Algorithms by A. Aho and J. Hopcroft and J. Ullman
    Regular Algebra and Finite Machines by J. H. Conway

    Related Problems


      
    Satisfiability
      
    String Matching



    This page last modified on 2008-07-10 .
    www.algorist.com