第一章预备知识 1
§1-1关系及其表示法 1
一、集合的乘积与划分 1
目 录 1
二、关系的概念 3
三、关系矩阵与方向图 5
§1-2关系中的路 7
一、路的概念 7
二、关系矩阵与路 9
一、自反、对称与传递的性质 15
§1-3关系的性质 15
二、等价关系与划分 20
§1-4映射与运算 22
一、映射 22
二、运算 24
§1-5半群 26
一、半群、独异半群的概念 26
二、半群的同态、同构及其性质 28
习题一 34
一、术语与记号 38
§2-1形式语言的基本概念 38
第二章形式语言引论 38
二、文法 40
§2-2文法与语言 43
§2-3 Chomsky分类 50
一、各类文法简介 50
二、2型文法的表示法 51
三、右线性文法与左线性文法 58
习题二 65
§3-1有限自动机的概念 68
一、有限自动机的定义及其表示法 68
第三章有限自动机与3型文法 68
二、FA的机器模型 75
三、DFA所识别的句子 77
四、NFA及其所识别的句子 80
§3-2 DFA与无ε移动的NFA的关系 83
§3-3 有ε移动的NFA 86
一、引言 86
二、ε闭包与？ 87
三、有ε移动与无ε移动的NFA的关系 90
§3-4正规式与正规集 94
一、正规式与正规集 94
二、正规式的运算性质 96
三、正规式所表示的语言的产生 98
§3-5正规集与FA 104
§3-6 3型文法与FA 114
§3-7 FA的化简 121
一、基本概念 121
二、与M等价的M/R的构造 126
§3-8不完全有限自动机与半群 132
§3-9 Moore机和Mealy机 137
习题三 144
§4-1语言在正规运算下的封闭性 150
第四章语言的性质 150
§4-2正规语言的封闭性 161
§4-3泵引理 166
习题四 168
第五章上下文无关文法与下推机 170
§5-1扩充的CFG 170
§5-2扩充的CFG与CFG的等价性 177
§5-3 CFG与CFL 181
一、CFG的化简 181
二、CFG的变换 187
三、CFL的泵引理 200
一、下推机的定义与模型 206
§5-4下推机 206
二、NPA与CFL 221
习题五 234
第六章句法分析 237
§6-1 二义性的进一步讨论 237
§6-2 Earley算法 246
§6-3 LL(k)文法与LR(k)文法 258
一、LL(k)文法的定义与性质 258
二、LR(k)文法的定义与性质 266
习题六 269
一、0型、1型文法的性质 270
第七章双向下推机与图灵机简介 270
§7-1 0型、1型文法与双向下推机 270
二、双向下推机与0型文法 278
三、线性有界自动机与1型文法 290
§7-2图灵机简介 294
一、图灵机的定义与模型 294
二、各种图灵机简介 300
三、图灵机与双向下推机 301
参考书目 305
习题解法提示 306