本书是普通高等教育“十一五”计算机类规划教材之一，主要介绍乔姆斯基文法体系的四类文法以及它们与有限自动机、下推自动机、线性界限自动机和图灵机之间的关系。此外，对语言的各种运算和封闭性质、判定问题及不可判定性以及确定的上下文无关语言与LR-文法也进行了讨论。书中还介绍了一些文法和自动机在文本编辑、编译程序、标注语言以及逻辑电路和时序电路设计中的应用。可作为高等学校计算机及相关专业研究生及高年级本科生课程教材，也可供从事计算机研究和开发的技术人员参考。

形式语言与自动机理论是计算机科学理论的重要基础。本书主要介绍乔姆斯基文法体系的四类文法以及它们与有限自动机、下推自动机、线性界限自动机和图灵机之间的关系。此外，对语言的各种运算和封闭性质、判定问题及不可判定性以及确定的上下文无关语言与LR-文法也进行了讨论。书中还介绍了一些文法和自动机在文本编辑、编译程序、标注语言以及逻辑电路和时序电路设计中的应用。

全书共分8章：第1章介绍语言及其表示；第2章介绍正规表达式、正规文法与有限自动机；第3章介绍上下文无关文法与下推自动机；第4章介绍图灵机；第5章介绍乔姆斯基文法体系；第6章介绍语言的运算与封闭性质；第7章介绍判定问题与不可判定性；第8章介绍确定的上下文无关语言和LR-文法。

本书可作为高等学校计算机及相关专业研究生及高年级本科生课程教材，也可供从事计算机研究和开发的技术人员参考。为方便教师教学，本书配有教学课件，欢迎选用本书作为教材的老师索取，索取邮箱：llm7785@sina.com。

前言

第1章 语言及其表示

 1.1 字母表、串和语言

1.1.1 字母表

1.1.2 串

1.1.3 语言

 1.2 文法

 1.3 语言识别器

 习题1

第2章 正规表达式、正规文法与有限自动机

 2.1 正规表达式与正规集

 2.2 正规文法和正规语言

 2.3 有限自动机

2.3.1 有限状态系统

2.3.2 确定的有限自动机

2.3.3 不确定的有限自动机

2.3.4 带ε-转换的不确定有限自动机

 2.4 正规表达式、正规文法与有限自动机的等价性

2.4.1 正规表达式与有限自动机的等价性

2.4.2 正规文法与有限自动机的等价性

2.4.3 把正规文法和有限自动机转化为正规表达式方程组求解

 2.5 正规语言的Pumping引理

 2.6 带输出的有限自动机

2.6.1 Moore机

2.6.2 Mea1y机

2.6.3 Moore机同Mea1y机的等价性

 2.7 有限自动机的化简

2.7.1 米希尔-尼罗德定理

2.7.2 最简有限自动机

2.7.3 有限自动机的化简方法

 2.8 正规表达式和有限自动机的应用

2.8.1 词法分析程序

2.8.2 文本编辑程序

2.8.3 文本搜索与字符串匹配

2.8.4 时序电路的分析与设计

 习题2

第3章 上下文无关文法与下推自动机

 3.1 上下文无关文法

 3.2 推导树

3.2.1 推导树的定义和例子

3.2.2 推导树与推导的关系

3.2.3 最左推导与最右推导

3.2.4 上下文无关文法的歧义性

 3.3 上下文无关文法的化简

3.3.1 无用字符

3.3.2 空产生式

3.3.3 单产生式

 3.4 乔姆斯基范式和格雷巴赫范式

3.4.1 乔姆斯基范式

3.4.2 格雷巴赫范式

 3.5 上下文无关语言的固有歧义性

 3.6 上下文无关文法的应用

3.6.1 语法分析程序

3.6.2 语法分析程序生成器

3.6.3 超文本标记语言

3.6.4 可扩展标记语言

 3.7 下推自动机

3.7.1 下推自动机的基本定义

3.7.2 两种不同方式接受语言的下推自动机的等价性

3.7.3 确定的下推自动机

 3.8 上下文无关文法与下推自动机的等价性

 3.9 上下文无关语言的Pumping引理

 习题3

第4章 图灵机

第5章 乔姆斯基文法体系

第6章 语言的运算与封闭性质

第7章 判定问题与不可判定性

第8章 确定的上下文无关语言

参考文献