形式语言与自动机

第1章 计算理论基础

1．1 集合的基本概念

1．1．1 集合的定义

1．1．2 集合的表示

1．1．3 集合间的关系

1．1．4 集合的运算

1．2 关系

1．2．1 二元关系

1．2．2 二元关系的性质

1．2．3 等价关系

1．2．4 递归定义与归纳证明

1．3 图与树

1．3．1 无向图

1．3．2 有向图

1．3．3 树

1．3．4 二叉树

1．4 三个重要概念

习题

第2章 文法与语言

2．1 启示

2．2 文法的形式定义

2．3 文法的构造

2．4 文法的Chomsky体系

习题

第3章 上下文无关文法及其语言

3．1 上下文无关文法

3．1．1 派生与派生树

3．1．2 文法的二义性

3．2 文法和语言的讨论

3．3 句法分析

3．3．1 最左派生和不确定性

3．3．2 文法图

3．3．3 广度优先自顶向下句法分析

3．3．4 深度优先自顶向下分析

3．3．5 自底向上分析

3．4 上下文无关文法的化简

3．4．1 无用符号

3．4．2 消除ε产生式

3．4．3 消除单一产生式

3．4．4 消除左递归

3．5 Chomsky范式

3．6 Greibach范式

习题

第4章 有穷状态自动机

4．1 语言的识别

4．2 有穷状态自动机的形式定义

4．3 确定的有穷自动机

4．4 状态转换图

4．5 不确定的有穷自动机

4．6 NFA与DFA的等价

4．7 带空转移的NFA

4．8 ε-NFA的确定化

4．9 DFA最小化

习题

第5章 正则语言和正则文法

5．1 正则表达式

5．1．1 正则表达式的定义

5．1．2 正则语言

5．2 有穷自动机和正则语言

5．2．1 正则表达式到有穷自动机

5．2．2 有穷自动机到正则表达式

5．3 正则文法和有穷自动机

5．3．1 正则文法

5．3．2 正则文法与NFA

习题

第6章 正则语言的性质

6．1 正则语言的封闭性

6．1．1 简单运算的封闭性

6．1．2 其他运算的封闭性

6．2 非正则语言的识别

6．2．1 鸽巢原理

6．2．2 泵引理

6．3 Myhill Nerode定理

6．4 正则语言的判定算法

习题

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

第8章 上下文无关语言的性质

第9章 图灵机

第10章 图灵机的其他模型

第11章 其他计算模型

参考文献

本书介绍了形式语言和自动机的基本理论和基本方法,主要内容包括计算理论基础、文法和语言、上下文无关文法及其语言、有穷状态自动机、正则语言与正则文法、正则语言的性质、下推自动机与上下文无关文法、上下文无关语言的性质、图灵机、图灵机的其他模型和其他计算模型等内容。本书可作为高等院校计算机科学与技术及相关专业的教材，也可作为教师、研究生或软件技术人员的参考书。