THE DECOMPOSITION OF FINITE STATE MACHINES
Abstract
A finite state machine is decomposed into the Cartesian product of two smaller finite state machines. A notation is developed to treat the problem, and principal results of Hartmanis and Yoeli are given with some extensions by the author. An addition operation on finite state machines is defined and it is shown that the product operation distributes over the addition operation. It is explained that the output-free finite state machine is equal to the sum of a set of single-input, output-free finite state machines. Some of the properties of transformation finite state machines, a special case of singleinput, output-free finite state machines, are discussed. The transformation finite state machine may be modeled by a transformation on a finite set. Some theorems are proved relating the structure of two transformation finite state machines to the structure of their product. Generating functions for transformation finite state machines are introduced, and it is shown how these may be used in obtaining the decomposition of a transformation finite state machine as the product of two smaller transformation finite state machines if such a decomposition exists.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1963
- Accession Number
- AD0427880
Entities
People
- Thomas V. Griffiths
Organizations
- Air Force Cambridge Research Laboratories