Most undergraduate books and research
literature describe methods based on compatible sets to reduce the number of
states of an incompletely specified synchronous/asynchronous sequential
machine. Deviating from this, incompatible sets of states are used in thispaper for this purpose. A simple technique is presented to generate all maximal
incompatible (compatible) sets from compatible (incompatible) pairs of states.
Generation of maximal incompatible sets has some advantages. The largest set
tells us about the number of states of the smallest machine. We can therefore
know how “good” is the minimal machine. We can know whether minimization is
necessary or not.
It is then minimized using an improved concept of minimality.
Symbols of the states of the minimal machine are assigned to states in
incompatible sets such that no two incompatible states get the same symbol.
This approach gives a minimal machine compared to some methods for synchronousmachines which try several possibilities. An example is given to show that a
conventional minimal machine can be nonminimal with respect to the minimality
introduced here. The improved minimality tends to give the smallest machine.
No comments:
Post a Comment