734
Modeling Arithmetic, Computation, and Languages
of 1); thus we should be in s 2 whenever the two most recent input symbols were
10, regardless of what came before. In particular, a string of 1010 should put us in
s 2 ; hence, the next-state function for s 3 with an input of 0 is s 2 . Similarly, we can
use s 1 to “remember” that the most recent input symbol received was 1, and that a
01 will take us to s 3 . In particular, 1011 should put us in s 1 ; hence, the next-state
function for s 3 with an input of 1 is s 1 . The rest of the next state function can be
determined the same way; Figure 9.7b shows the complete state graph.
figure 9.7
Notice that the machine is in state s 2 at the end of an input of 0110 and at the end of
an input of 011010—in fact, at the end of any input ending in 10; yet s 2 cannot distinguish between these inputs. Each state of M represents a class of indistinguishable
input histories, s 3 being the state representing all inputs ending in 101.
PrACtiCe 48 Draw the state graph for a machine producing an output of 1 exactly when the input string
received to that point ends in 00.
■
Now we want to see exactly what sets finite-state machines can recognize.
Remember that recognition is possible because machine states have a limited
memory of past inputs. Even though the machine is finite, a particular input signal
can affect the behavior of a machine “forever.” However, not every input signal
can do so, and some classes of inputs require remembering so much information
that no machine can detect them.
To avoid writing down outputs, we will designate those states of a finitestate machine with an output of 1 as final states and denote them in the state graph
with a double circle. Then we can give the following formal definition of recognition, where I* denotes the set of finite-length strings over the input alphabet.
Definition finitE-stAtE MAChinE rECoGnition
A finite-state machine M with input alphabet I recognizes a subset S of I* if M,
beginning in state s 0 and processing an input string a, ends in a final state if and
only if a [ S.
Modeling Arithmetic, Computation, and Languages
of 1); thus we should be in s 2 whenever the two most recent input symbols were
10, regardless of what came before. In particular, a string of 1010 should put us in
s 2 ; hence, the next-state function for s 3 with an input of 0 is s 2 . Similarly, we can
use s 1 to “remember” that the most recent input symbol received was 1, and that a
01 will take us to s 3 . In particular, 1011 should put us in s 1 ; hence, the next-state
function for s 3 with an input of 1 is s 1 . The rest of the next state function can be
determined the same way; Figure 9.7b shows the complete state graph.
figure 9.7
Notice that the machine is in state s 2 at the end of an input of 0110 and at the end of
an input of 011010—in fact, at the end of any input ending in 10; yet s 2 cannot distinguish between these inputs. Each state of M represents a class of indistinguishable
input histories, s 3 being the state representing all inputs ending in 101.
PrACtiCe 48 Draw the state graph for a machine producing an output of 1 exactly when the input string
received to that point ends in 00.
■
Now we want to see exactly what sets finite-state machines can recognize.
Remember that recognition is possible because machine states have a limited
memory of past inputs. Even though the machine is finite, a particular input signal
can affect the behavior of a machine “forever.” However, not every input signal
can do so, and some classes of inputs require remembering so much information
that no machine can detect them.
To avoid writing down outputs, we will designate those states of a finitestate machine with an output of 1 as final states and denote them in the state graph
with a double circle. Then we can give the following formal definition of recognition, where I* denotes the set of finite-length strings over the input alphabet.
Definition finitE-stAtE MAChinE rECoGnition
A finite-state machine M with input alphabet I recognizes a subset S of I* if M,
beginning in state s 0 and processing an input string a, ends in a final state if and
only if a [ S.