Machines with Memory - Models of Computation: Exploring the Power of Computing - page 92

3.1 Finite-State Machines
The finite-state machine (FSM) has a set of states, one of which is its initial state. At each unit
of time an FSM is given a letter from its input alphabet. This causes the machine to move
from its current state to a potentially new state. While in a state, the FSM produces a letter
from its output alphabet. Such a machine computes the function defined by the mapping
from its initial state and strings of input letters to strings of output letters. FSMs can also be
used to accept strings, as discussed in Chapter 4 . Some states are called final states. A string
is recognized (or accepted) by an FSM if the last state entered by the machine on that input
string is a final state. The language recognized (or accepted) by an FSM is the set of strings
accepted by it. We now give a formal definition of an FSM.

DEFINITION 3.1.1 A finite-state machine (FSM) M is a seven-tuple M =(Σ , Ψ , Q , δ , λ , s ,
F ) ,where Σ is the input alphabet , Ψ is the output alphabet , Q is the finite set of states ,
δ : Q

Ψ is the output function , s is the initial
state (which may be fixed or variable), and F is the set of final states ( F

× → Q is the next-state function , λ : Q →

Σ

Q ) .IftheFSMis
given input letter a when in state q ,itentersstate δ ( q , a ) .Whileinstate q it produces the output
letter λ ( q ) .
The FSM M accepts the string w

⊆

Σ ∗ if the last state entered by M on the input string w
starting in state s is in the set F .M recognizes (or accepts ) the language L consisting of the set
of such strings.
When the initial state of the FSM M is not fixed, for each integer TM maps the initial state
s and its T external inputs w 1 , w 2 , ... , w T onto its T external outputs y 1 , y 2 , ... , y T and the
final state q ( T ) . We say that in T steps the FSM M computes the function f ( T )
M

∈

Σ T : Q × →

Ψ T . It is assumed that the sets Σ , Ψ ,and Q are encoded in binary so that f ( T )
M

Q × is a binary

function.

The next-state and output functions of an FSM, δ and λ , can be represented as in Fig. 3.1 .
We visualize these functions taking a state value from a memory and an input value from an
external input and producing next-state and output values. Next-state values are stored in the
memory and output values are released to the external world. From this representation an
actual machine (a sequential circuit) can be constructed (see Section 3.3 ). Once circuits are
constructed for δ and λ , we need only add memory units and a clock to construct a sequential
circuit that emulates an FSM.

Output

Input

δ , λ

Memory

Figure 3.1 The finite-state machine model.