Handouts and course notes provided by the instructors. Some of these
will be given out in class.
The texts on reserve and course webpage are not
required reading. I regard the webpage as a repository for ``static''
information such as syllabus info, problem sets, parts of answer keys,
and useful links--all material that once placed on the webpage can be
relied upon not to change. The newsgroup is for dynamic
information--most typical are questions and helps on problem sets.
Hence I regard the newsgroup as higher-priority than the webpage, and
you are well advised to read it at least twice a week.
The reserve texts will include my own personal copies of the following
books, on 2-hour reserve. My copy of Martin (2nd ed.) is AWOL; I will
place my copy of the 3rd ed. and the rest on reserve when I am done with it.
- (a)
-
John C. Martin, Introduction to Languages and the Theory of
Computation, 3rd ed.,
(New York: McGraw-Hill, 1997). The text I used prior to Sipser,
i.e. in the 1990s. It covers more
aspects of the course material in detail than Sipser's text does, taking
almost twice as many pages and including topics such as
``DFA minimization'' that Sipser cuts. The only one I intend to cover
that is not in Sipser is the Myhill-Nerode Theorem, a
UB(!)-Cornell product that is IMHO
far superior to the "Pumping Lemma"---you
you will have special notes on this.
- (b)
-
J. Glenn Brookshear, Theory of Computation: Formal Languages,
Automata, and Complexity (Addison-Wesley, 1989).
The text closest to Sipser in basic nature and coverage, written
by someone with a generally more ``applied'' point of view.
- (c)
-
Harry R. Lewis and Christos H. Papadimitriou,
Elements of the Theory of Computation, 2nd. ed.
(Prentice Hall, 1998). A nice revision and slimming of a text that used to
be rather complicated and ``heavy.'' Possibly the best text
(aside from the classic 1979 mainly-graduate text by Hopcroft and Ullman,
which is not on reserve) for those who really dig this material.
Has also recently been used as a CSE396 text.
These are my personal copies, and are for in-library reserve only.
There are various other texts in SEL that may be worth your reading.
The only excursions outside Sipser's text that I am currently planning
are (i) Myhill-Nerode, (ii) extra lectures on induction proofs
when we hit context-free grammars leading to the topic of
Structural Induction, and (iii) a lecture or two on how
Turing Machines can simulate assembly language, and thus
simulate ``Pascal and Lisp'' as the text asserts on page 142.
Next: Organization and Course Policies
Up: CSE396 Course Information
Previous: No Title