Journal of Formalized Mathematics
Volume 6, 1994
University of Bialystok
Copyright (c) 1994
Association of Mizar Users
Minimization of Finite State Machines
-
Miroslava Kaloper
-
University of Alberta, Department of Computing Science
-
Piotr Rudnicki
-
University of Alberta, Department of Computing Science
Summary.
-
We have formalized deterministic finite state machines closely
following the textbook [10], pp. 88-119 up to the minimization
theorem. In places, we have changed the approach presented in the book
as it turned out to be too specific and inconvenient.
Our work also revealed several minor mistakes in the book.
After defining a structure for an outputless finite state machine,
we have derived the structures for the transition assigned output
machine (Mealy) and state assigned output machine (Moore). The machines
are then proved similar, in the sense that for any Mealy (Moore) machine
there exists a Moore (Mealy) machine producing essentially
the same response for the same input. The rest of work is then done
for Mealy machines. Next, we define equivalence of machines,
equivalence and $k$-equivalence of states, and characterize a process of
constructing for a given Mealy machine, the machine equivalent to it
in which no two states are equivalent. The final, minimization
theorem states:
\begin{quotation}
\noindent
{\bf Theorem 4.5:} Let {\bf M}$_1$ and {\bf M}$_2$ be reduced, connected
finite-state machines. Then the state graphs of {\bf M}$_1$ and {\bf M}$_2$
are isomorphic if and only if {\bf M}$_1$ and {\bf M}$_2$ are equivalent.
\end{quotation}
and it is the last theorem in this article.
This work was partially supported by NSERC Grant OGP9207.
MML Identifier:
FSM_1
The terminology and notation used in this paper have been
introduced in the following articles
[15]
[7]
[19]
[2]
[17]
[12]
[9]
[18]
[16]
[14]
[20]
[4]
[6]
[5]
[8]
[3]
[1]
[13]
[11]
-
Preliminaries
-
Definitions and Terminology
-
Mealy and Moore Machines
-
Equivalence of States and Machines
-
The Reduction of a Mealy Machine
-
Machine Isomorphism
-
Reduced and Connected Machines
-
Machine Union
-
The Minimization Theorem
Bibliography
- [1]
Grzegorz Bancerek.
Cardinal numbers.
Journal of Formalized Mathematics,
1, 1989.
- [2]
Grzegorz Bancerek.
The fundamental properties of natural numbers.
Journal of Formalized Mathematics,
1, 1989.
- [3]
Grzegorz Bancerek and Krzysztof Hryniewiecki.
Segments of natural numbers and finite sequences.
Journal of Formalized Mathematics,
1, 1989.
- [4]
Czeslaw Bylinski.
Functions and their basic properties.
Journal of Formalized Mathematics,
1, 1989.
- [5]
Czeslaw Bylinski.
Functions from a set to a set.
Journal of Formalized Mathematics,
1, 1989.
- [6]
Czeslaw Bylinski.
Partial functions.
Journal of Formalized Mathematics,
1, 1989.
- [7]
Czeslaw Bylinski.
Some basic properties of sets.
Journal of Formalized Mathematics,
1, 1989.
- [8]
Czeslaw Bylinski.
The modification of a function by a function and the iteration of the composition of a function.
Journal of Formalized Mathematics,
2, 1990.
- [9]
Agata Darmochwal.
Finite sets.
Journal of Formalized Mathematics,
1, 1989.
- [10]
P. J. Denning, J. B. Dennis, and J. E. Qualitz.
\em Machines, Languages, and Computation.
Prentice-Hall, 1978.
- [11]
Katarzyna Jankowska.
Transpose matrices and groups of permutations.
Journal of Formalized Mathematics,
4, 1992.
- [12]
Beata Padlewska.
Families of sets.
Journal of Formalized Mathematics,
1, 1989.
- [13]
Konrad Raczkowski and Pawel Sadowski.
Equivalence relations and classes of abstraction.
Journal of Formalized Mathematics,
1, 1989.
- [14]
Andrzej Trybulec.
Domains and their Cartesian products.
Journal of Formalized Mathematics,
1, 1989.
- [15]
Andrzej Trybulec.
Tarski Grothendieck set theory.
Journal of Formalized Mathematics,
Axiomatics, 1989.
- [16]
Andrzej Trybulec.
Tuples, projections and Cartesian products.
Journal of Formalized Mathematics,
1, 1989.
- [17]
Michal J. Trybulec.
Integers.
Journal of Formalized Mathematics,
2, 1990.
- [18]
Wojciech A. Trybulec.
Groups.
Journal of Formalized Mathematics,
2, 1990.
- [19]
Zinaida Trybulec.
Properties of subsets.
Journal of Formalized Mathematics,
1, 1989.
- [20]
Edmund Woronowicz.
Relations and their basic properties.
Journal of Formalized Mathematics,
1, 1989.
Received November 18, 1994
[
Download a postscript version,
MML identifier index,
Mizar home page]