738
Modeling Arithmetic, Computation, and Languages
example 33
Let M be given by the state table of Table 9.3. Although the state table contains the
same information as the state graph (Figure 9.9), the graph shows us at a glance
that state s 2 can never be reached from the starting state s 0 . If we simply remove
state s 2 and its associated arcs, we have the state graph of Figure 9.10 for a machine M′ with one less state than M that behaves exactly like M; that is, it gives the
same output as M for any input string.
table 9.3
present state
next state
output
present input
0
1
s 0
s 1
s 3
0
s 1
s 3
s 0
0
s 2
s 1
s 3
1
s 3
s 0
s 1
1
figure 9.9
figure 9.10
■
Because the state graph of a finite-state machine is a directed graph, it has
an associated adjacency matrix. Warshall’s algorithm (Section 7.1) can be used to
detect unreachable states.
PrACtiCe 52 What state(s) is/are unreachable from s 0 in the machine of Table 9.4? Try to get your answer directly from the state table.
table 9.4
present state
next state
output
present input
0
1
s 0
s 1
s 4
0
s 1
s 4
s 1
1
s 2
s 2
s 2
1
s 3
s 3
s 1
0
s 4
s 0
s 0
1