Information Technology Reference
In-Depth Information
Start
q
0
/
0
0
1
q
1
/
0
q
2
/
1
0
1
0
1
q
3
/
0
q
4
/
1
q
5
/
1
q
6
/
0
0
1
0
1
0
1
0
1
q
7
/
0
q
8
/
1
q
9
/
1
q
10
/
0
q
11
/
1
q
12
/
0
q
13
/
0
q
14
/
1
Figure 3.4
A fifteen-state FSM that computes the
EXCLUSIVE OR
of three inputs as a subfunc-
tion of
f
(
3
M
obtained by deleting all outputs except the third.
3.1.4 Interconnections of Finite-State Machines
Later in this chapter we examine a family of FSMs characterized by a computational unit
connected to storage devices of increasing size. The random-access machine that has a CPU
of small complexity and a random-access memory of large but indeterminate size is of this
type. The Turing machine having a fixed control unit that moves a tape head over a potentially
infinite tape is another example.
This idea is captured by the
interconnection of synchronous FSMs
.SynchronousFSMs
read inputs, advance from state to state, and produce outputs in synchronism. We allow two
or more synchronous FSMs to be interconnected so that some outputs from one FSM are
supplied as inputs of another, as illustrated in Fig.
3.5
. Below we generalize Theorem
3.1.1
to
a pair of synchronous FSMs. We model random-access machines and Turing machines in this
fashion when each uses a finite amount of storage.
THEOREM
3.1.3
Let
f
(
T
)
M
2
be a function computed in
T
steps by a pair of interconnected syn-
chronous FSMs,
M
1
=(Σ
1
,
Ψ
1
,
Q
1
,
δ
1
,
λ
1
,
s
1
,
F
1
)
and
M
2
=(Σ
2
,
Ψ
2
,
Q
2
,
δ
2
,
λ
2
,
s
2
,
F
2
)
.
M
1
×
Output
Output
Input
M
1
M
2
Input
Figure 3.5
The interconnection of two finite-state machines in which one of the three outputs
of
M
1
is supplied as an input to
M
2
and two of the three outputs of
M
2
are supplied to
M
1
as
inputs.
Search WWH ::
Custom Search