- 形式语言与自动机导论(原书第7版)/计算机科学丛书
- - 作者：(美)彼得·林茨//苏珊·H.罗杰|责编:曲熠|译者:王春宇//袁永峰
  - 出版社：机械工业
  - ISBN：9787111767527
  - 出版日期：2025/02/01
  - 页数：477
- 售价：51.6

内容大纲
本书是理论计算机科学方面的经典教材，主要讨论形式语言与自动机理论、可计算性理论和计算复杂性理论等内容。本书强调定义和定理的准确性和严谨性，但在形式化证明中又非常注重符合直觉的理解，避免多余的数学细节。本书分为理论和应用两个部分。本书可帮助读者熟悉计算机科学的基础和原理，加强严格的形式化数学证明的能力，适合高等院校计算机科学及相关专业的学生学习，也适合理论计算机科学方向的研究人员参考。
作者介绍
目录
译者序
前言
理论部分
  第1章  计算理论概论
    1.1  数学预备知识和符号表示
      1.1.1  集合
      1.1.2  函数和关系
      1.1.3  图和树
      1.1.4  证明方法
    1.2  三个基本概念
      1.2.1  语言
      1.2.2  文法
      1.2.3  自动机
    1.3  应用*
  第2章  有穷自动机
    2.1  确定的有穷接受器
      2.1.1  确定的接受器和转移图
      2.1.2  语言和DFA的语言
      2.1.3  正则语言
    2.2  非确定的有穷接受器
      2.2.1  非确定的接受器的定义
      2.2.2  为什么需要非确定性？
    2.3  确定与非确定的有穷接受器的等价性
    2.4  减少有穷自动机中状态的化简*
  第3章  正则语言和正则文法
    3.1  正则表达式.
      3.1.1  正则表达式的形式定义
      3.1.2  正则表达式所关联的语言
    3.2  正则表达式和正则语言的联系
      3.2.1  正则表达式表示正则语言
      3.2.2  正则语言的正则表达式
      3.2.3  描述简单模式的正则表达式
    3.3  正则文法
      3.3.1  左线性文法和右线性文法
      3.3.2  右线性文法生成正则语言
      3.3.3  正则语言的右线性文法
      3.3.4  正则语言和正则文法的等价性
  第4章  正则语言的性质
    4.1  正则语言的封闭性
      4.1.1  简单集合运算的封闭性
      4.1.2  其他运算的封闭性
    4.2  正则语言的基本问题
    4.3  识别非正则语言
      4.3.1  鸽巢原理的使用
      4.3.2  泵引理
  第5章  上下文无关语言
    5.1  上下文无关文法
      5.1.1  上下文无关文法示例
      5.1.2  最左推导和最右推导
      5.1.3  推导树

      5.1.4  句型和推导树的关系
    5.2  解析和歧义性
      5.2.1  解析和成员资格
      5.2.2  文法和语言的歧义性
    5.3  上下文无关文法和程序设计语言
  第6章  上下文无关文法的化简和范式
    6.1  文法转换的方法
      6.1.1  有用的代入规则
      6.1.2  消除无用的产生式
      6.1.3  消除λ-产生式
      6.1.4  消除单元产生式
    6.2  两种重要的范式
      6.2.1  乔姆斯基范式
      6.2.2  格雷巴赫范式
    6.3  上下文无关文法的成员资格判定算法*
  第7章  下推自动机
    7.1  非确定的下推自动机
      7.1.1  下推自动机的定义
      7.1.2  下推自动机接受的语言
    7.2  下推自动机和上下文无关语言
      7.2.1  上下文无关语言对应的下推自动机
      7.2.2  下推自动机对应的上下文无关文法
    7.3  确定的下推自动机和确定的上下文无关语言
    7.4  确定的上下文无关语言的文法*
  第8章  上下文无关语言的性质
    8.1  两个泵引理
      8.1.1  上下文无关语言的泵引理
      8.1.2  线性语言的泵引理
    8.2  上下文无关语言的封闭性和判定算法
      8.2.1  上下文无关语言的封闭性
      8.2.2  上下文无关语言的一些可判定性质
  第9章  图灵机
    9.1  标准的图灵机
      9.1.1  图灵机的定义
      9.1.2  作为语言接受器的图灵机
      9.1.3  作为转换器的图灵机
    9.2  完成复杂任务的组合图灵机
    9.3  图灵论题
  第10章  图灵机的其他模型
    10.1  对图灵机的小改动
      10.1.1  自动机类的等价性
      10.1.2  可驻停图灵机
      10.1.3  半无穷带图灵机
      10.1.4  离线图灵机
    10.2  具有更复杂存储的图灵机
      10.2.1  多带图灵机
      10.2.2  多维图灵机
    10.3  非确定的图灵机
    10.4  通用图灵机
    10.5  线性界限自动机

  第11章  形式语言和自动机的层次结构
    11.1  递归语言和递归可枚举语言
      11.1.1  非递归可枚举语言
      11.1.2  一个非递归可枚举的语言
      11.1.3  一个递归可枚举但非递归的语言
    11.2  无限制文法
    11.3  上下文有关文法和语言
      11.3.1  上下文有关语言和线性界限自动机
      11.3.2  递归语言和上下文有关语言的关系
    11.4  乔姆斯基层次结构
  第12章  算法计算的限制
    12.1  图灵机无法解决的问题
      12.1.1  可计算性和可判定性
      12.1.2  图灵机停机问题
      12.1.3  不可判定问题的归约
    12.2  递归可枚举语言的不可判定问题
    12.3  波斯特对应问题
    12.4  上下文无关语言的不可判定问题
    12.5  关于效率的问题
  第13章  其他计算模型
    13.1  递归函数
      13.1.1  原始递归函数
      13.1.2  阿克曼函数
      13.1.3  μ-递归函数
    13.2  波斯特系统
    13.3  重写系统
      13.3.1  矩阵文法
      13.3.2  马尔可夫算法
      13.3.3  L-系统
  第14章  计算复杂性概述
    14.1  计算的效率
    14.2  图灵机模型和复杂性
    14.3  语言族和复杂性类
    14.4  复杂性类P和NP
    14.5  几个NP问题
    14.6  多项式时间归约
    14.7  NP完全性和一个未解决的问题
应用部分
  第15章  编译器和解析
    15.1  编译器
    15.2  自顶向下和自底向上的解析
    15.3  FIRST函数
    15.4  FOLLOW函数
  第16章  LL解析
    16.1  上下文无关文法转换为NPDA
      16.1.1  LL解析的下推自动机
      16.1.2  LL解析中将上下文无关文法转换为NPDA的算法
    16.2  LL(1)分析表
    16.3  LL(1)解析算法
    16.4  LL(k)解析

  第17章  LR解析
    17.1  上下文无关文法转换为NPDA
    17.2  项和闭包
    17.3  DFA建模LR解析栈
    17.4  LR(1)分析表
      17.4.1  LR(1)的解析动作
      17.4.2  LR(1)分析表算法
    17.5  LR(1)解析算法
    17.6  带有λ-产生式的LR(1)解析
    17.7  LR(1)解析冲突
附录A  有穷状态转换器
附录B  实用工具JFLAP
练习题选解
参考文献

内容大纲

作者介绍

目录

同类热销排行榜

推荐书目