91.304 -
Foundations of Computer Science - Fall 2008
Prof. Robert Lechner, Professor
Emeritus/Adjunct,
Computer Science Department
University of Massachusetts Lowell, Lowell, MA
RJLRef: $PH/09s304/textbooks.htm (last updated 090123)
Michael Sipser: Introduction to the Theory of Computation. 2nd ed. Boston, MA:
Thomson/PWS/Course Technology, 2005. ISBN: 0534950973. (The Second
edition contains new homework problems and solutions.)
Please Note: Errata including trivial
punctuation and capitalization in Sipser 2Ed are corrected at
http://www-math.mit.edu/~sipser/itoc-errs2.1.html
Non-trivial corrections cited in that URI occur on these (2ed) pages :
{22, 65, 83, 92,, 93, 95, 96, 97, 98109, 116, 125, 129, 131, 132, 133, 134, 139, 145, 160, 162, 163, 166, 180, 181, 184, 186, 196, 197, 210, 213, 214, 215, 2223, 225, 228, 229, 244, 263, 281, 281, 284, 295, 298, 300, 301, 305, 307, 318, 320, 328, 329, 331, 332, 341, 347, 354, 358, 360, 362, 363, 370, 370, 371, 376, 377-378, 383, 386, 391, 395, 396, 397, 398, 399, 400, 403, 408, 410, 413, 415, 416, 413, 421}.
UML's prior 07s304 text: Hopcroft, Motwani, and Ullman: Introduction to Automata Theory, Languages, and Computation. 3rd edition. Addison-Wesley, ISBN 0-321-45536-3.
This text may also be helpful. It has a similar structure
with many more details on machines and languages than Sipser Chapters 1 - 3, but
much less material on Complexity Theory.