《形式语言》

第一章预备知识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 有ε移动的NFA86

一、引言86

二、ε闭包与？87

三、有ε移动与无ε移动的NFA的关系90

§3-4正规式与正规集94

一、正规式与正规集94

二、正规式的运算性质96

三、正规式所表示的语言的产生98

§3-5正规集与FA104

§3-6 3型文法与FA114

§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扩充的CFG170

§5-2扩充的CFG与CFG的等价性177

§5-3 CFG与CFL181

一、CFG的化简181

二、CFG的变换187

三、CFL的泵引理200

一、下推机的定义与模型206

§5-4下推机206

二、NPA与CFL221

习题五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