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

Contents (PDF format)

1. Preliminaries
2. Definitions and Terminology
3. Mealy and Moore Machines
4. Equivalence of States and Machines
5. The Reduction of a Mealy Machine
6. Machine Isomorphism
7. Reduced and Connected Machines
8. Machine Union
9. 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.