Section 9.3 Finite-State Machines
729
the actions of the computer. On a clock pulse, input can be read, which can change
some of the storage locations and thus change the state of the machine to a new state.
What the new state is will depend on what the input was, as well as what the previous
state was. If these two factors are known, the change is predictable and nonrandom.
Because the contents of certain storage cells are available as output, the state of the
machine determines its output. In this way, over a succession of clock pulses, the
machine produces a sequence of outputs in response to a sequence of inputs.
Definition
The finite-state machine is a model that captures the characteristics of a computer.
As you read the definition, look for the following properties in the behavior of our
abstract machine:
1. Operations of the machine are synchronized by discrete clock pulses.
2. The machine proceeds in a deterministic fashion; that is, its actions in
response to a given sequence of inputs are completely predictable.
3. The machine responds to inputs.
4. There is a finite number of states that the machine can attain. At any given
moment, the machine is in exactly one of these states. Which state it will
be in next is a function of both the present state and the present input. The
present state, however, depends on the previous state and input, while the
previous state depends on its previous state and input, and so on, going all
the way back to the initial configuration. Thus, the state of the machine at
any moment serves as a form of memory of past inputs.
5. The machine is capable of output. The nature of the output is a function of the
present state of the machine, meaning that it also depends on past inputs.
Definition finitE-stAtE MAChinE
M = 3S, I, O, f S , f O 4 is a finite-state machine if S is a finite set of states, I is a
finite set of input symbols (the input alphabet), O is a finite set of output symbols
(the output alphabet), and f S and f O are functions where f S : S × I S S and
f O : S S O). The machine is always initialized to begin in a fixed starting state s 0 .
The function f S is the next-state function. It maps a (state, input) pair to a
state. Thus, the state at clock pulse t i+1 , state(t i+1 ), is obtained by applying the
next-state function to the state at time t i and the input at time t i :
state(t i+1 ) = f S (state(t i ), input(t i ))
The next-state function is indeed a function, so for any (state, input) pair,
there is a unique next state. The function f O is the output function. When f O is
applied to a state at time t i , we get the output at time t i :
output(t i ) = f O (state(t i ))
Notice that the effect of applying function f O is available instantly, but the effect
of applying function f S is not available until the next clock pulse.
Examples of finite-state Machines
To describe a particular finite-state machine, we have to define the three sets and
two functions involved.
729
the actions of the computer. On a clock pulse, input can be read, which can change
some of the storage locations and thus change the state of the machine to a new state.
What the new state is will depend on what the input was, as well as what the previous
state was. If these two factors are known, the change is predictable and nonrandom.
Because the contents of certain storage cells are available as output, the state of the
machine determines its output. In this way, over a succession of clock pulses, the
machine produces a sequence of outputs in response to a sequence of inputs.
Definition
The finite-state machine is a model that captures the characteristics of a computer.
As you read the definition, look for the following properties in the behavior of our
abstract machine:
1. Operations of the machine are synchronized by discrete clock pulses.
2. The machine proceeds in a deterministic fashion; that is, its actions in
response to a given sequence of inputs are completely predictable.
3. The machine responds to inputs.
4. There is a finite number of states that the machine can attain. At any given
moment, the machine is in exactly one of these states. Which state it will
be in next is a function of both the present state and the present input. The
present state, however, depends on the previous state and input, while the
previous state depends on its previous state and input, and so on, going all
the way back to the initial configuration. Thus, the state of the machine at
any moment serves as a form of memory of past inputs.
5. The machine is capable of output. The nature of the output is a function of the
present state of the machine, meaning that it also depends on past inputs.
Definition finitE-stAtE MAChinE
M = 3S, I, O, f S , f O 4 is a finite-state machine if S is a finite set of states, I is a
finite set of input symbols (the input alphabet), O is a finite set of output symbols
(the output alphabet), and f S and f O are functions where f S : S × I S S and
f O : S S O). The machine is always initialized to begin in a fixed starting state s 0 .
The function f S is the next-state function. It maps a (state, input) pair to a
state. Thus, the state at clock pulse t i+1 , state(t i+1 ), is obtained by applying the
next-state function to the state at time t i and the input at time t i :
state(t i+1 ) = f S (state(t i ), input(t i ))
The next-state function is indeed a function, so for any (state, input) pair,
there is a unique next state. The function f O is the output function. When f O is
applied to a state at time t i , we get the output at time t i :
output(t i ) = f O (state(t i ))
Notice that the effect of applying function f O is available instantly, but the effect
of applying function f S is not available until the next clock pulse.
Examples of finite-state Machines
To describe a particular finite-state machine, we have to define the three sets and
two functions involved.