自动机理论与应用

出版时间：2011-12  出版社：清华大学出版社  作者：里奇  页数：525  
Tag标签：无  

内容概要

　　《自动机理论与应用》阐述了计算科学的优美理论基础，通过演示计算理论在现代硬件和软件系统设计中的影响，把理论知识带到了现实实践之中。本书介绍了关键概念的应用，为读者在实际工作中使用计算理论提供实际指导。本书讨论的应用包括：程序设计语言、编译器、网络技术、自然语言处理、人工智能、计算生物学、安全性、博弈论、商业规则建模、标识语言、Web搜索等。本书既适合作为自动机理论课程的教程，也是相关专业人员的重要参考用书。
　　

作者简介

作者：(美国)里奇 (Elaine Rich) 译者：米哲伟 武桂香 等

书籍目录

第1部分简 介
　第1章 为什么学习计算理论
　第2章 语言与字符串
　第3章 语言层次
　第4章 计算
第2部分 有限状态机与正则语言
　第5章 有限状态机
　第6章 正则表达式
　第7章 正则文法
　第8章 正则与非正则语言
　第9章 正则语言的算法与决策过程
　第10章 小结与参考资料
第3部分 上下文无关语言与压栈自动机
　第11章 上下文无关文法
　第12章 压栈自动机
　第13章 上下文无关与非上下文无关语言
　第14章 上下文无关语言的算法与决策过程
　第15章 上下文无关解析
　第16章 小结与参考资料
第4部分 图灵机与不可确定性
　第17章 图灵机
　第18章 church-turing命题
　第19章 停止问题的不可解决性
　第20章 可确定与半确定语言
　第21章 可确定性与不可确定性证明
　第22章 不明显提图灵机问题的语言的可确定性
　第23章 无限制文法
　第24章 chomsky层次及其他
　第25章 可计算函数
　第26章 小结与参考资料
第5部分 复 杂度
　第27章 复杂度分析简介
　第28章 时间复杂度类
　第29章 空间复杂度类
　第30章 难题的实用解
　第31章 小结与参考资料
参考资料

章节摘录

版权页：插图：可以把第4部分的工作看成探索计算的极限。我们考虑了许多不同的可计算模型，这些模型试图回答这样的问题，“能计算什么？”其中有些模型很相似。例如，Post生产系统和无限制文法都是通过开始符和一组改写字符串的生产规则来定义语言。尽管有差别（Post生产系统利用变量，要匹配整个字符串，而无限文法只用常量，可以匹配子串），但两个形式是一致的：都定义SD语言类。同样，图灵机和标记系统也差不多，一个用磁带和可移动的读／写头，一个用先进先出队列。但它们的差别也不大，两都可以相互模拟。

编辑推荐

《世界著名计算机教材精选:自动机理论与应用》由清华大学出版社出版。

用户评论 (总计5条)

•   不错，毕竟这种书少有
•   毕竟是知名的自动机理论教材
•   很好的专业书，印刷和质量都很好
•   感觉编辑错误不少，我只是读了钱150页，按照个人理解的，感觉有很多错误。如状态q0错误写成q1,还需要和英文原版对照才能完全确认出错。目前发现有好多处
•   买了这么多次书。。第一次评论。。。这书居然把附录阉割了！！逼我再买本原版？！