原书第3版 算 机 科 学 丛 书 华章教育 语言与机器 计算机科学理论导论 （美）ThomasA.Sudkamp著孙家骊等译 THIRD EDITION An Introduction to the Theory of Computer Science anguages and Machines Thomas A. Sudkamp Languages and Machines An Introduction to the Theory of Computer Science Third Edition 机械工业出版社 ChinaMachinePress 语言与机器计算机科学理论导论 （原书第3版） 理论计算机科学是推动计算机技术和应用向前发展的巨大动力。形式语言、自动机 可计算性、计算复杂性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之 本书由美国莱特州立大学计算机科学及工程系的ThomasA.Sudkamp教授编写，是介 绍这些内容的优秀教材。 全书不仅介绍了计算机科学的基础，探讨了算法计算的能力和局限；而且还通过概念 的严格表述，以及使用通俗的例子来解释定理，从而帮助学生提高数学论证能力。书中每 章后面都有一些练习，通过这些练习使学生加深对本章内容的理解。 第三版亮点： 超过100个新的习题和示例 强调问题表述和问题归约的重要性 显著地扩展了计算复杂性的覆盖面 增加了用问题归约证明NP完全性的章节 ，处理NP完全问题时给出了近似算法 作 Thomas A. Sudkamp 是美国莱特州立大学计算机科学 者简 及工程系的教授，他的研究领域 广泛，包括近似推理、人工智能、数理逻辑、建模软计算的应用、复杂问题领域 介 的决策制定以及不确定、不精确信息和知识发掘的机器学习。Sudkamp教授目前 还担任IEEETransactionsonSystem，Man，andCybernetics和lEEE TransactionsonFuzzySystems的副编辑，InternationalJournalofApproximate Reasoning和FuzzySetsandSystems的领域编辑。他也曾经担任过北美模糊信 息处理协会（NAFIPS）的主席以及国际模糊系统联盟（IFSA）的副主席。 wailiwesley www.PearsonEd.com 上架指导：计算机/计算机理论 -22634-5 投稿热线：（010）88379604 购书热线：（010）68995259，68995264 OPEARSON 读者信箱：[email protected] Education 华章网站http://www.hzbook.com 97871111226345 网上购书：www.china-pub.com ISBN978-7-111-22634-5 定价：49.00元 封设计·锡彬 原书第3版 TP3/560 计算机 书 2008 语言与机器 计算机科学理论导论 （美）ThomasA.Sudkamp 著孙家等译 An Introduction to the Theory of Computer Science anguages ano Machines Languages ana viachines AnIntroduction to the Theory of Computer Science ThirdEdition 机械工业出版社 China Machine Press 本书是计算理论方面的优秀教材之一，包括上下文无关文法、上下文无关文法范式、 有限自动机、正则语言的性质、下推自动机和上下文无关语言、图灵机、图灵可计算函 数、乔姆斯基层次、判定问题与丘奇图灵机、不可判定性、Mu一递归函数、时间复杂性、 库克定理、NP-完全问题、LL（k）文法以及LR（k）文法等问题。本书不仅介绍了计算机科 学的基础，而且通过概念的严格表述，以及使用通俗的例子来阐释定理，从而帮助学生提 高数学论证能力以及对计算理论知识的全面深人的理解。书中每章后面都有附有大量习 题，通过完成这些习题，学生可以加深对本章内容的理解。 本书可以用作计算机科学、计算机工程及其相关专业的教材，也可以作为从事计算理 论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。 Simplified Chinese edition copyright2008 by Pearson Education Asia Limited and China MachinePress. Original English language title:Languages and Machines:An Introduction to the Theory of Computer Science,ThirdEdition （ISBN0-321-32221-5)by ThomasA.Sudkamp,Copy- right2006by Pearson Education,Inc. All rights reserved. Published by arrangement with the original publisher,Pearson Education,Inc.,publishing 本书封面贴有PearsonEducation（培生教育出版集团）激光防伪标签，无标签者不得 销售。 版权所有，侵权必究。 本书法律顾问北京市展达律师事务所 本书版权登记号：图字：01-2006-1948 图书在版编目（CIP）数据 语言与机器：计算机科学理论导论（原书第3版）/（美）萨德坎普（Sudkamp，T.A） 著；孙家骗等译.一北京：机械工业出版社，2008.3 书名原文：Languages and Machines：An Introduction to the Theory of Computer Science, ThirdEdition （计算机科学丛书） ISBN978-7-111-22634-5 I.语I.①萨.·②孙I.计算机科学IV.TP3 中国版本图书馆CIP数据核字（2007）第164490号 机械工业出版社（北京市西城区百万庄大街22号邮政编码100037） 责任编辑：李南丰 2008年3月第1版第1次印刷 184mm×260mm·25.75印张 标准书号：ISBN978-7-111-22634-5b1T 定价：49.00元 凡购本书，如有倒页、脱页缺页，由本社发行部调换 本社购书热线（010）68326294 出版者的话 文艺复兴以降，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学的 各个领域取得了垒断性的优势；也正是这样的传统，使美国在信息技术发展的六十多年间名 家辈出、独领风。在商业化的进程中，美国的产业界与教育界越来越紧密地结合，计算机 学科中的许多泰山北斗同时身处科研和教学的最前线，由此而产生的经典科学著作，不仅 划了研究的范畴，还揭藥了学术的源变，既遵循学术规范，又自有学者个性，其价值并不会 因年月的流逝而减退 近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日 益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略 上显得举足轻重。在我国信息技术发展时间较短、从业人员较少的现状下，美国等发达国家 在其计算机科学发展的几十年间积淀的经典教材仍有许多值得借鉴之处。因此，引进一批国 外优秀计算机教材将对我国计算机教育事业的发展起积极的推动作用，也是与世界接轨、建 设真正的世界一流大学的必由之路。 机械工业出版社华章图文信息有限公司较早意识到“出版要为教育服务”。自1998年开始， 华章公司就将工作重点放在了选、移译国外优秀教材上。经过几年的不懈努力，我们与 PrenticeHall，Addison-Wesley，McGraw-Hill，MorganKaufmann等世界著名出版公司建立了 良好的合作关系，从它们现有的数百种教材中甄选出Tanenbaum，Stroustrup，Kernighan， JimGray等大师名家的一批经典作品，以“计算机科学丛书”为总称出版，供读者学习、研 究及皮藏。大理石纹理的封面，也正体现了这套丛书的品位和格调。 “计算机科学丛书”的出版工作得到了国内外学者的鼎力襄助，国内的专家不仅提供了中 肯的选题指导，还不辞劳苦地担任了翻译和审校的工作；而原书的作者也相当关注其作品在 中国的传播，有的还专程为其书的中译本作序。迄今，“计算机科学丛书”已经出版了近百个 品种，这些书籍在读者中树立了良好的口碑，并被许多高校采用为正式教材和参考书籍，为 进一步推广与发展打下了坚实的基础。 随着学科建设的初步完善和教材改革的逐渐深化，教育界对国外计算机教材的需求和应 用都步入一个新的阶段。为此，华章公司将加大引进教材的力度，在“华章教育”的总规划 之下出版三个系列的计算机教材：除“计算机科学丛书”之外，对影印版的教材，则单独开 辟出“经典原版书库”；同时，引进全美通行的教学辅导书“Schaum'sOutlines”系列组成 “全美经典学习指导系列”。为了保证这三套丛书的权威性，同时也为了更好地为学校和老师 们服务，华章公司聘请了中国科学院、北京大学、清华大学、国防科技大学、复且大学、上 海交通大学、南京大学、浙江大学、中国科技大学、哈尔滨工业大学、西安交通大学、中国 人民大学、北京航空航天大学、北京邮电大学、中山大学、解放军理工大学、郑州大学、湖 北工学院、中国国家信息安全测评认证中心等国内重点大学和科研