Section 9.3 Finite-State Machines
743
table 9.6
present state
next state
output
present input
0
1
A
A
D
0
B
A
A
0
C
D
A
1
D
C
B
1
example 37
We will minimize M where M is given by the state table of Table 9.7.
table 9.7
present state
next state
output
present input
0
1
0
3
1
1
1
4
1
0
2
3
0
1
3
2
3
0
4
1
0
1
The 0-equivalence classes of M are
50, 2, 46, 51, 36
States 0 and 2 under input 1 go to states 1 and 0, which are not 0-equivalent. The
1-equivalence classes of M are
506, 52, 46, 51, 36
No further refinement is possible. Let
A = 506
B = 52, 46
C = 51, 36
The reduced machine is shown in Table 9.8.
table 9.8
present state
next state
output
present input
0
1
A
C
C
1
B
C
A
1
C
B
C
0