Information Technology Reference
In-Depth Information
y
1,1
y
1,2
y
2,1
y
2,2
y
T
,1
y
T
,2
x
1
x
2
x
T
c
1
c
2
δ
1
δ
1
λ
1
δ
1
λ
1
λ
1
...
q
0
q
1
q
2
q
T
v
1
v
2
v
T
d
1
u
1,1
u
1,2
u
2,1
u
2,2
u
T
,1
u
T
,2
δ
2
λ
2
δ
2
λ
2
δ
2
λ
2
p
0
p
1
p
2
p
T
Figure 3.6
A circuit simulating
T
steps of the two synchronous interconnected FSMs shown
in Fig.
3.5
. The top row of circuits simulates a
T
-step computation by
M
1
and the bottom row
simulates a
T
-step computation by
M
2
. 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. The states of
M
1
on the
initial and
T
successive steps are
q
0
,
q
1
,
...
,
q
T
.Thoseof
M
2
are
p
0
,
p
1
,
...
,
p
T
.
Let
C
Ω
(
δ
,
λ
)
and
D
Ω
(
δ
,
λ
)
be the size and depth of encodings of the next-state and output func-
tions. Then, the circuit size and depth over the basis
Ω
of any function
f
computed by the pair
M
1
×
M
2
in
T
steps(thatis,asubfunctionof
f
(
T
)
M
1
×M
2
) satisfy the following inequalities:
C
Ω
(
f
)
≤
T
[
C
Ω
(
δ
1
,
λ
1
)+
C
Ω
(
δ
2
,
λ
2
)]
T
[max(
D
Ω
(
δ
1
,
λ
1
)
,
D
Ω
(
δ
2
,
λ
2
))]
Proof
The construction that leads to this result is suggested by Fig.
3.6
.Weunwindboth
FSMs and connect the appropriate outputs from one to the other to produce a circuit that
computes
f
(
T
)
M
1
×
D
Ω
(
f
)
≤
M
2
. Observe that the number of gates in the simulated circuit is
T
times the
sum of the number of gates, whereas the depth is
T
times the depth of the deeper circuit.
3.1.5 Nondeterministic Finite-State Machines
The finite-state machine model described above is called a
deterministic FSM
(DFSM) be-
cause, given a current state and an input, the next state of the FSM is uniquely determined.
A potentially more general FSM model is the
nondeterministic
FSM (NFSM) characterized
by the possibility that several next states can be reached from the current state for some given
input letter.
One might ask if such a model has any use, especially since to the untrained eye a non-
deterministic machine would appear to be a dysfunctional deterministic one. The value of an
NFSM is that it may recognize languages with fewer states and in less time than needed by a
DFSM. The concept of nondeterminism will be extended later to the Turing machine, where
Search WWH ::
Custom Search