形式语言PDF电子书下载

第一章预备知识 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