Mealy's model of a sequential machine is assumed and a relation of ``compatibility'' of states is introduced to further the analysis of such machines. In the event that input restrictions exist it is often possible to effect combinations of states under this relation in addition to those permitted under equivalence of states, a relation previously studied. Compatibility of states is analyzed by an iterative technique, rigorously established, which makes it possible to determine readily connection matrices of simpler ``compatible'' machines.

In this paper we indicate briefly how the methods of the algebraic solution of Markov chains with constant transition probabilities apply to the analysis of sequential machines. Mealy's model of a sequential machine is assumed. A stochastic matrix is associated with each such machine to provide a starting point for the analysis. ``Closed'' sets of states are then characterized, for example, by the appropriate theorems about Markov chains. A technique is formulated for reducing the connection matrix of any sequential machine to a canonical form.

This paper begins with Mealy's model of a sequential machine and introduces a ``connection matrix'' which describes the machine completely. The ``equivalence'' of states of such a machine may be analyzed systematically by an iterative technique, the validity of which is rigorously established. Once equivalence is completely analyzed, it is a simple matter to write the connection matrix for the simplest equivalent machine. The process is not difficult to execute, even in complex cases, and could be programmed for a computer.

This paper presents the general concept of a weighted directed graph which we call a net. Illustrative examples leading up to the definition of a net indicate its applicability to a wide variety of problems in communication and network theory. A number of theorems concerning the proper paths of a net are established. A non-arithmetic matrix calculus is developed to facilitate computations and formalize proofs. In later papers, the techniques presented here will be exploited in the study of the theory of sequential machines.