计 算 机科 学 丛 书 HZBOOKS 华章教育 CENGAGE 原书第3版 Learning 计算理论导引 迈克尔·西普塞（MichaelSipser） [美] 麻省理工学院 段磊唐常杰 等译 四川大学 ntroduction to theTheory of Computation Third Edition Introduction' to the Theory of Computation 3rdedition MichaelSipser 机械工业出版社 ChinaMachinePress 计算理论导引 原书第3版 Introductionto theTheory of Computation Third Edition 本书由计算理论领域的知名权威MichaelSipser所撰写。他以独特的视角，系统地介绍了计算理论的三 个主要内容：自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的，同时对可计算性 和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学 原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵 的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是 某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并用一节的篇幅对确定型上下文无 关语言进行了直观而不失严谨的介绍。此外，对练习和问题进行了全面更新，每章末均有习题选答。 作者简介 迈克尔·西普塞（MichaelSipser）美国麻省理工学院应用数学系教授，计算机科学和 人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作三十多 年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。 上架指导：计算机计算理论 CENGAGE ISBN 978-7-111-49971-8 Learning www.cengageasia.com 投稿热线：（010）88379604 华章网站：www.hzbook.com 客服热线：（010）8837899188361066 网上购书：www.china-pub.com 91787 11111499718> 购书热线：（010）68326294 8837964968995259 数字阅读：www.hzmedia.com.cn 定价：69.00元 封设计锡彬 原书第3版 计算理论导弓 著 麻省理工学院 四川大学 Introduction to the Theory of Computation Third Edition Introduction to the Theory of Computation 3rd edition 机械工业出版社 ChinaMachinePress 图书在版编目（CIP）数据 计算理论导引（原书第3版）／（美）西普塞（Sipser，M.）著；段磊等译，一北京：机械工 业出版社，2015.6 （计算机科学丛书） 书名原文：IntroductiontotheTheoryofComputation，ThirdEdition ISBN978-7-111-49971-8 I.计II.西②段··III.计算技术-理论IV.TP301 中国版本图书馆CIP数据核字（2015）第077899号 本书版权登记号：图字：01-2014-0329 Michael Sipser: Introduction to the Theory of Computation, Third Edition Copyright 2013 by Cengage Learning. Original editionpublishedby Cengage Learning.All Rights reserved. China Machine Press is authorized by Cengage Learning to publish and distribute exclusively this simplifed Chinese edition. This edition is authorized for sale in the People's Republic of China only(excludingHongKong,MacaoSARandTaiwan).Unauthorized export of this edition is a violation of the Copyright Act.No part of this publication may be reproduced or distributed by any means, or stored in a database or retrieval system, without the prior written permission of the publisher. Cengage Learning Asia Pte. Ltd. 151LorongChuan,#02-08NewTechPark,Singapore556741 本书原版由圣智学习出版公司出版。版权所有，盗印必究。 本书中文简体字翻译版由圣智学习出版公司授权机械工业出版社独家出版发行。此版本仅限在中华 人民共和国境内（不包括中国香港、澳门特别行政区及中国台湾）销售。未经授权的本书出口将被视为 违反版权法的行为。未经出版者预先书面许可，不得以任何方式复制或发行本书的任何部分。 本书封面贴有CengageLearning防伪标签，无标签者不得销售。 本书是计算理论领域的经典著作，以注重思路、深人引导为特色，系统地介绍计算理论的三大主要内 容：自动机与语言、可计算性理论和计算复杂性理论。同时，重点讲解了可计算性和计算复杂性理论中的 某些高级内容。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。 新版的一大亮点是用一节的篇幅对确定型上下文无关语言进行了直观而不失严谨的介绍。 本书叙述由浅人深、详略得当，重点突出，不拘泥于技术细节，可作为高等院校计算机专业高年级本 科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。 出版发行：机械工业出版社（北京市西城区百万庄大街22号邮政编码：100037） 责任编辑：迟振春 责任校对：董纪丽 印 刷：冀城市京瑞印刷有限公司 版 次：2015年8月第1版第1次印刷 开 本：185mm×260mm1/16 印 张：19.5 书 号：ISBN978-7-111-49971-8 定 价：69.00元 凡购本书，如有缺页、倒页、脱页，由本社发行部调换 客服热线：（010）88378991 88361066 投稿热线：（010）88379604 购书热线：（010）6832629488379649 68995259 读者信箱：[email protected] 版权所有·侵权必究 封底无防伪标均为盗版 本书法律顾问：北京大成律师事务所韩光／邹晓东 出版者的话 Introduction to the Theory of Computation, 3e 文艺复兴以来，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学的 各个领域取得了垒断性的优势；也正是这样的优势，使美国在信息技术发展的六十多年间名 家辈出、独领风骚。在商业化的进程中，美国的产业界与教育界越来越紧密地结合，计算机 学科中的许多泰山北斗同时身处科研和教学的最前线，由此而产生的经典科学著作，不仅撃 划了研究的范畴，还揭示了学术的源变，既遵循学术规范，又自有学者个性，其价值并不会 因年月的流逝而减退。 近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日 益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略 上显得举足轻重。在我国信息技术发展时间较短的现状下，美国等发达国家在其计算机科学 发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此，引进一批国外优秀计 算机教材将对我国计算机教育事业的发展起到积极的推动作用，也是与世界接轨、建设真正 的世界一流大学的必由之路。 机械工业出版社华章公司较早意识到“出版要为教育服务”。自1998年开始，我们就 将工作重点放在了避选、移译国外优秀教材上。经过多年的不懈努力，我们与Pearson， McGraw-Hill，Elsevier，MIT，JohnWiley&Sons，Cengage等世界著名出版公司建立了良 好的合作关系，从他们现有的数百种教材中甄选出AndrewS.Tanenbaum，BjarneStroustrup， Brain W.Kernighan,DennisRitchie,Jim Gray,AfredV.Aho,JohnE.Hopcroft,Jeffrey D. Ullman, Abraham Silberschatz, William Stallings, Donald E. Knuth, John L. Hennessy, LarryL.Peterson等大师名家的一批经典作品，以“计算机科学丛书”为总称出版，供读者 学习、研究及珍藏。大理石纹理的封面，也正体现了这套丛书的品位和格调。 “计算机科学丛书”的出版工作得到了国内外学者的鼎力相助，国内的专家不仅提供了 中肯的选题指导，还不辞劳苦地担任了翻译和审校的工作；而原书的作者也相当关注其作品 两百个品种，这些书籍在读者中树立了良好的口