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'

Implementations

  • Grail: finite automata and regular expressions (C++) (rating 9)
  • Fire-Engine and Spare-Parts String and Language Algorithms (C++) (rating 8)
  • Handbook of Algorithms and Data Structures (Pascal) (rating 5)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 1)

    Related Problems

  • Satisfiability
  • String Matching

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .