Homework Set 2
DUE: April 12,1999, 6:30 pm
Collaboration Policy:
Unless noted otherwise, you may collaborate with other CSE599 students
on the homework. You must spend at least 15 minutes working on a problem
before seeking assistance. Collaboration means that you may discuss the
problems and make notes during the discussion, but you may not look at
other student’s work when writing up your homework. Your homework represents
your own work—the homework must show that you understand the material and
have worked as an individual on every problem. You may not divide up the
task of doing the problem sets in the interpretation of collaboration.
Late Homework Policy:
The weekly assignments are due at the beginning of class. Assignments
handed in after class will incur a 10% penalty; the penalty will increase
by 10% for each additional day late.
Reading:
Feynman pgs. 52–129
Please show all of your work, and remember, your solutions must be legible. The points for each problem are noted on the problem statement.
1. (10 pts) Design two DFAs (deterministic finite automata). Both take serial binary strings as their input, and compute the parity of the digits indicated below. All strings are terminated by an "e" symbol (i.e. an "end" symbol). Both automata should halt and output "even" or "odd" when they see the symbol "e". (Instructor’s note: These DFAs form a part of a machine that generates parity bits for a Hamming error-correcting code).
(b) Can you construct a TM that computes whether two DFAs are equivalent?
(c) Can you construct a TM that, given the radius of a circle, computes the area.
(d) Suppose that you have two unclocked spiking circuits (i.e. circuits that generate delta functions—zero-width voltage spikes—at some arbitrary times t), two delay lines (also of arbitrary length), and a coincidence detector that generates an output spike when its two input spikes are coincident. Can you simulate this arrangement with a DFA? How about with a Turing machine? Does your answer change if the spikes have finite width?