1.7.7 Finite State Machine Minimization
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.
Recommended Books
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Practical Algorithms for Programmers
Handbook of Algorithms and Data Structures
The Design and Analysis of Computer Algorithms
Regular Algebra and Finite Machines
