Information Technology Reference
In-Depth Information
1
0
q
0
/
0
q
1
/
1
0
1
Start
Figure 3.2
A finite-state machine computing the
EXCLUSIVE OR
of its inputs.
AnexampleofanFSMisshowninFig.
3.2
. Its input and output alphabets and state
sets are
Σ=
{
0, 1
}
,
Ψ=
{
0, 1
}
,and
Q
=
{
q
0
,
q
1
}
, respectively. Its next-state and output
functions,
δ
and
λ
,aregivenbelow.
qσδ
(
q
,
σ
)
q
0
q
λ
(
q
)
q
0
q
0
0
0
q
0
q
1
q
1
1
1
q
1
q
1
0
q
1
1
q
0
The FSM has initial state
q
0
and final state
q
1
. As a convenience we explicitly identify final
states by shading, although in practice they can be associated with states producing a particular
output letter.
Each state has a label
q
j
/v
j
,where
q
j
isthenameofthestateand
v
j
is the output produced
while in this state. The initial state has an arrow labeled with the word “start” pointing to
it. Clearly, the set of strings accepted by this FSM are those containing an odd number of
instancesof1. Thusitcomputesthe
EXCLUSIVE OR
function on an arbitrary number of
inputs.
While it is conventional to think of the finite-state machine as a severely restricted com-
putational model, it is actually a very powerful one. The random-access machine (RAM)
described in Section
3.4
is an FSM when the number of memory locations that it contains
is bounded, as is always so in practice. When a program is first placed in the memory of
the RAM, the program sets the initial state of the RAM. The RAM, which may or may not
read external inputs or produce external outputs, generally will leave its result in its memory;
that is, the result of the computation often determines the final state of the random-access
machine.
TheFSMdefinedaboveiscalleda
Moore machine
because it was defined by E.F. Moore
[
223
] in 1956. An alternative FSM, the
Mealy machine
(defined by Mealy [
215
] in 1955),
has an output function
λ
∗
:
Q
Ψ
that generates an output on each transition from
one state to another. This output is determined by both the state in which the machine resides
before the state transition and the input letter causing the transition. It can be shown that the
two machine models are equivalent (see Problem
3.6
): any computation one can do, the other
can do also.
×
Σ
→
Search WWH ::
Custom Search