Permissible Behaviors in a Network of FSMs

A behavior is a set of input/output strings that can be produced or represented by a DFSM. An NDFSM will represent in general more than one behavior and more than one DFSM may represent the same behavior. Given a synchronous system of interacting FSMs and a specification, consider the problem of finding the complete set of permissible behaviors at a particular component of the system 1. The problem is illustrated in Figure 6.1, where M₁ is the FSM associated with the component to be optimized, M₂ represents the behavior of the rest of the system, and M gives the specification. In a variant of the problem, the roles of M₁ and M₂ are inverted. Figures 6.2-(a) and 6.2-(b) show how the variant is reduced to the original problem. Although x is a direct input to M₂ in Figure 6.2-a, one can view x as feeding through M₁ via a straight wire connection, as drawn in Figure 6.2-b; similarly the output z can be seen as passing through M₁.