Download pdf-file

DESIGN OF STATE DIAGRAM FACILITIES IN SCED
19
Figure 19. A state diagram with one superstate
H B A K
A
b
d
B a
C a b c
D a
c d
E
c d
Table 1.
Generally, in state diagram matrices we show only those states and transitions which
are interesting while forming superstates. Since each superstate has to include at
least two substates, every column in a state diagram matrix contains at least two
transitions.
If we demand that all states, which have similarly labeled leaving transitions which
enter the same state, have to be associated as substates of the same superstate,
there will be only four dierent possibilities to form a superstate:
1) states B, C and D (because of the transitions with label a)
2) states A and C (because of the transitions with label b)
3) states C, D and E (because of the transitions with label c)
4) states A, D and E (because of the transitions with label d)
All these possibilities are mutually contradictional. If we choose one of the possibilities 1, 2 and 4, the number of transitions needed will be reduced by two. The
second possibility reduces the amount of transitions needed by one. So, the possibilities 1, 2 and 4 are equally good. Yet, these are not the optimal solutions. The
maximal reduction can be obtained e.g. by forming rst superstate for states B and
C, second superstate for states A, D and E and third superstate for states D and
E. In this case the reduction in the number of transitions is (2-1)+(3-1)+(2-1)=4.
For generating the total number of superstate candidates in an arbitrary state diagram we concentrate on states and transitions shown in the state diagram matrix.
Let m be the number of dierent labels on transitions. Further, i is used as an
index for these labels. Each superstate candidate must contain at least two and at
most n substates, where n is the number of transitions with ith label. It is easy
i
i