目录

第1章预备知识与记号1

1.1语言的概念1

1.1.1字母表1

1.1.2字符串及其相关运算1

1.1.3字母表上的幂运算与闭包运算2

1.1.4语言2

1.1.5关于语言的运算2

1.2常用证明技术3

1.2.1基本证明方法3

1.2.2归纳证明方法4

练习6

第2章上下文无关文法与上下文无关语言7

2.1上下文无关文法的基本概念7

2.1.1简单例子7

2.1.2上下文无关文法的四个基本要素8

2.1.3上下文无关文法的定义与记号8

2.2归约与推导9

2.2.1归约9

2.2.2推导10

2.3上下文无关文法的语言与上下文无关语言11

2.4上下文无关文法的设计12

2.5文法与语言的Chomsky分类15

2.6语法分析树16

2.7归约、推导与分析树之间的关系17

2.8文法和语言中的二义性18

2.8.1文法的二义性18

2.8.2语言中的二义性20

2.8.3无二义文法的设计21

2.8.4消除二义性的几种文法变换方法21

练习24

第3章正规表达式与正规语言28

3.1正规表达式28

3.2正规语言30

3.3正规表达式的设计30

3.4正规表达式与正规文法的等价性31

3.4.1从正规表达式到正规文法31

3.4.2从正规文法到正规表达式33

3.5正规表达式的代数定律36

3.5.1正规表达式的几组代数定律36

3.5.2代数定律的具体化37

练习39

第4章有限状态自动机42

4.1确定有限自动机42

4.1.1有限状态自动机及其表示42

4.1.2确定有限自动机及其语言44

4.1.3确定有限自动机的设计46

4.2非确定有限自动机48

4.3确定与非确定有限自动机的等价性51

4.4有限自动机的一个应用——文本搜索53

4.5带ε转移的非确定有限自动机55

4.6（确定）有限自动机的最小化58

练习64

第5章有限自动机与正规表达式的关系68

5.1从正规表达式构造等价的εNFA68

5.2从DFA构造等价的正规表达式71

练习75

第6章正规语言的性质与运算77

6.1针对正规语言的Pumping引理77

6.1.1Pumping引理77

6.1.2Pumping引理的一个应用79

6.2有关正规语言的几个判定性质80

6.2.1判定正规语言是否为空80

6.2.2判定正规语言中是否包含特定的字符串81

6.2.3判定两个正规语言是否相等81

6.3关于正规语言的封闭运算81

6.3.1正规语言的并、（星）闭包和连接82

6.3.2正规语言的补、交和差82

6.3.3正规语言的反向84

6.3.4正规语言的同态85

6.3.5正规语言的反同态86

6.3.6应用88

练习91

第7章下推自动机94

7.1下推自动机的基本概念94

7.1.1下推自动机的定义94

7.1.2下推自动机的语言95

7.2下推自动机的设计97

7.3下推自动机的另一种定义99

7.4两种定义的等价性100

练习102

第8章上下文无关文法下推自动机104

8.1从上下文无关文法构造等价的下推自动机104

8.2从下推自动机构造等价的上下文无关文法107

8.3小结109

练习109

第9章确定下推自动机111

9.1确定下推自动机的概念111

9.2确定下推自动机与正规语言112

9.3前缀性质及空栈接受的确定下推自动机112

9.4确定下推自动机与上下文无关语言113

9.5确定下推自动机与无二义文法114

练习116

第10章上下文无关文法的变换与范式117

10.1几种常用的文法变换117

10.1.1消去无用符号117

10.1.2消去ε产生式120

10.1.3消去Unit产生式122

10.1.4同时消去无用符号、ε产生式和Unit产生式125

10.1.5代换非终结符125

10.1.6消除左递归126

10.2Chomsky范式130

10.3Greibach范式133

练习136

第11章上下文无关语言的性质与运算139

11.1针对上下文无关语言的Pumping引理139

11.1.1Pumping引理139

11.1.2Pumping引理用于判定某些语言不是上下文无关语言141

11.2Ogden引理142

11.3有关上下文无关语言的几个判定性质144

11.3.1判定上下文无关语言是否为空145

11.3.2判定上下文无关语言中是否包含特定的字符串145

11.3.3有关上下文无关语言的几个不可判定问题147

11.4关于上下文无关语言的封闭运算148

11.4.1上下文无关语言的替换148

11.4.2上下文无关语言的并、闭包（星闭包和正闭包）和连接150

11.4.3上下文无关语言的同态151

11.4.4上下文无关语言的反向151

11.4.5上下文无关语言的交、补和差152

11.4.6上下文无关语言与正规语言的交152

11.4.7上下文无关语言的反同态153

11.4.8应用155

练习155

第12章自动机与分析文法159

12.1语法分析基础159

12.1.1自顶向下语法分析159

12.1.2自底向上语法分析162

12.2下推自动机的扩展及归约自动机167

12.2.1扩展的下推自动机167

12.2.2归约自动机+168

12.2.3确定的归约自动机+171

12.3自动机与语法分析172

12.3.1下推自动机与自顶向下语法分析172

12.3.2归约自动机与自底向上的语法分析+173

12.4LL(k) 分析文法与LL语法分析176

12.4.1LL(k)文法177

12.4.2LL(1)文法179

12.4.3基于LL(1)文法的语法分析183

12.4.4LL(k)文法和语言的几个判定问题及其层次关系187

12.5LR(k)分析文法与LR语法分析188

12.5.1LR(k)文法188

12.5.2LR语法分析基础191

12.5.3其他常见的LR分析方法210

12.5.4LR文法与确定的归约自动机+216

12.5.5LR(k)文法和语言的若干性质、判定问题222

练习224

第13章图灵机与递归可枚举语言229

13.1图灵机的概念与定义229

13.2定义图灵机的语言233

13.3递归可枚举语言与递归语言234

13.4图灵机的设计及编程技巧235

13.4.1基本图灵机的设计235

13.4.2图灵机的编程技巧238

13.5扩展的图灵机240

13.5.1多带图灵机241

13.5.2非确定图灵机242

13.6受限的图灵机244

13.6.1具有半无穷带的图灵机244

13.6.2多栈机246

13.6.3计数器机248

13.7图灵机与普通计算机251

13.7.1普通计算机模拟图灵机251

13.7.2多带图灵机模拟普通计算机251

练习254

第14章计算理论初步258

14.1对角语言与通用语言258

14.1.1图灵机的编码和输入串的编号258

14.1.2对角语言259

14.1.3递归语言和递归可枚举语言的补运算260

14.1.4通用语言261

14.2问题与语言263

14.3问题的归约263

14.4有关递归可枚举语言的判定问题265

14.4.1判定递归可枚举语言的空与非空265

14.4.2Rice定理267

14.5Post 对应问题268

14.6关于上下文无关语言和文法的几个不可判定问题269

14.7P问题与NP问题272

14.8NP完全问题与NP难问题273

练习274

参考文献276