Exercise 8.11 (Definition of a Non-deterministic Finite-state Machine).

Define the allowed behavior of a non-deterministic finite-state machine by means of a global list of phases. In the 6 states (s1, s2, s3) equal to (000),

(100), (110), (010), (011), and (001) the deterministic behavior must be identical to the global list of phases given in Fig. 8.6. In the additional states

(s1, s2, s3) equal to (111) and (101) any of the necessary other states may be reached in the following time step. In these two states any output pattern is allowed. Practical tasks:

1 Why is the finite-state machine specified in this exercise a non-deterministic machine?

2 Prepare a PRP that defines a space large enough to allow the design of this non-deterministic finite-state machine completely.

3 Define the global list of phases for the non-deterministic finite-state machine, described in this Exercise, as object number 1.