This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications. This new edition comes with Gradiance, an online assessment tool developed for computer science. Gradiance is the most advanced online assessment tool developed for the computer science discipline. With its innovative underlying technology, Gradiance turns basic homework assignments and programming labs into an interactive learning experience for students. By using a series of "root questions" and hints, it not only tests a student's capability, but actually simulates a one-on-one teacher-student tutorial that allows for the student to more easily learn the material. Through the programming labs, instructors are capable of testing, tracking, and honing their students' skills, both in terms of syntax and semantics, with an unprecedented level of assessment never before offered. For more information about Gradiance, please visit www.aw.com/gradiance.

本书由计算机理论领域的知名权威Michaael Sipser所撰写。他以独特的视角，系统地介绍了计算机理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。约大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并对课堂测试题进行了全面的更新，每章末均有样例解答。 本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

本书是计算理论领域的经典著作，被国外多所大学选用为教材。本书以注重思路、深入引导为特色，系统地介绍计算理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。同时，对可计算性和计算复杂性理论中的某些高级内容作了重点讲解。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。新版的一大亮点是增加了更多习题、教辅资料和部分习题解答，更加有利于教学。 全书叙述由浅入深、详略得当，重点突出，不拘泥于技术细节。可作为计算机专业高年级本科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。

本书是关于形式语言、自动机理论和计算复杂性方面的经典教材，是三位理论计算大师的巅峰之作，现已更新到第3版。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的，陸质、图灵机、不可判定性以及难解问题等内容。 本书已被世界许多著名大学采用为计算机理论课程的教材或教学参考书，适合用作国内高校计算机专业高年级本科生或研究生的教材，还可供从事理论计算工作的研究人员参考。

本书内容十分丰富，涉及了集合论、指称语义、操作语义、公理语义、归纳原理、完备性、域论、信息系统、不确定性和并行性、不完备性和不可判定性等内容。同时，每章都包含了丰富的难度不等的练习。 　　本书是以作者在剑桥大学和Aarhus大学的讲义为基础编写的，是一本难得的形式语义学方面的经典著作。书中为初学程序设计语言的语义与逻辑的读者提供了必需的数学知识，介绍了支撑程序设计语言形式语义的数学理论、方法和概念，这些知识可以用于创造、形式化和证明规则，从而可以描述和推导各类程序设计语言的各种成分和性质。 本书内容十分丰富，涉及了集合论、指称语义、操作语义、公理语义、归纳原理、完备性、域论、信息系统、不确定性和并行性、不完备性和不可判定性等内容。同时，每章都包含了丰富的难度不等的练习。 本书适合作为高等院校计算机专业高年级本科生和研究生形式语义课程的教材，也可作为软件开发人员的参考书。

This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set.