本书《语言与机器:计算机科学理论导论》是一部深入探讨计算机科学基础的著作,它分为五个主要部分,分别为基础、语言、文法、自动机和计算复杂性,以及确定型语法分析。以下是各部分的主要内容概要:
第1章数学预备知识,涵盖了集合论、笛卡儿积、关系和函数、等价关系、可数与不可数集合、对角化和自反、递归定义以及数学归纳等内容。
第2章语言介绍了字符串和语言的概念,以及正则集合和表达式的使用。
第3章上下文无关文法详细讨论了文法与语言的关系,以及正则文法、验证和文法的二义性等内容。
第4章介绍上下文无关文法的转换规则,如消去入规则和乔姆斯基范式。
第5章有限自动机探讨了确定型和非确定型自动机,以及它们在语言接收中的应用。
第8章图灵机介绍了标准图灵机及其在语言接收中的角色,以及不同类型的图灵机。
第11章丘奇—图灵论题涉及判定问题、归约和不可判定性等内容。
第14章时间复杂性探讨了复杂性度量和图灵机的时间复杂性。
第15章P、NP和库克定理讨论了非确定型图灵机的时间复杂性和复杂性类的关系。
第18章语法分析引论介绍了语法图和自顶向下与自底向上分析方法。
第19章LR(k)文法详细讲解了LL(k)和LR(k)文法的构造和分析器。
《语言与机器:计算机科学理论导论》介绍了计算机科学的基础知识,以及各种算法计算的能力和局限性。本书通过大量示例,以一种直观、易懂的方式阐释了计算机科学理论的概念及相关数学知识。第3版还扩展介绍了自动机理论、计算理论和计算复杂性等内容。本书可作为计算机及相关专业的计算机科学理论课程的教材。