Information Technology Reference
In-Depth Information
Show that the subfunction of
f
FA
obtained by fixing
c
i
=
0 and deleting
c
i
+
1
is the
EXCLUSIVE OR
of the variables
x
i
and
y
i
.
3.6 It is straightforward to show that every Moore FSM is a Mealy FSM. Given a Mealy
FSM, show how to construct a Moore FSM whose outputs for every input sequence are
identical to those of the Mealy FSM.
3.7 Find a deterministic FSM that recognizes the same language as that recognized by the
nondeterministic FSM of Fig.
3.8
.
3.8 Write a program in a language of your choice that writes the straight-line program
described in Fig.
3.3
for the FSM of Fig.
3.2
realizing the
EXCLUSIVE OR
function.
SHALLOW FSM CIRCUITS
3.9 Develop a representation for states in the
m
-word,
b
-bit random-access memory so that
its next-state mappings form a semigroup.
Hint:
Show that the information necessary to update the current state can be succinctly
described.
3.10 Show that matrix multiplication is associative.
SEQUENTIAL CIRCUITS
3.11 Show that the circuit of Fig.
3.15
computes the functions defined in the tables of
Fig.
3.14
.
Hint:
Section
2.2
provides a method to produce a circuit from a tabular description of
a binary function.
3.12 Design a sequential circuit (an
electronic lock
) that enters an accepting state only when
it receives some particular four-bit sequence that you specify.
3.13 Design a sequential circuit (a
modulo-
p
counter
) that increments a binary number by
one on each step until it reaches the integer value
p
,atwhichpointitresetsitsvalueto
zero. You should assume that
p
is not a power of 2.
3.14 Give an efficient design of an
incrementing/decrementing counter
,asequentialcir-
cuit that increments or decrements a binary number modulo 2
n
.Specifythemachine
as an FSM and determine the number of gates in the sequential circuit in terms of
n
.
RANDOM-ACCESS MACHINES
3.15 Given a straight-line program for a Boolean function, describe the steps taken to com-
pute it during fetch-and-execute cycles of a RAM. Determine whether jump instruc-
tions are necessary to execute such programs.
3.16 Consulting Theorem
3.4.1
, determine whether jump instructions are necessary for all
RAM computations. If not, what advantage accrues to using them?
3.17 Sketch a RAM program using time and space
O
(
n
)
that recognizes strings of the form
{
0
m
1
m
|
≤
m
≤
n
}
1
.
Search WWH ::
Custom Search