形式语言与自动机理论

《形式语言与自动机理论》由会员分享，可在线阅读，更多相关《形式语言与自动机理论（858页珍藏版）》请在金锄头文库上搜索。

1、11/20/12 1形式语言与自动机理论形式语言与自动机理论 Formal Languages and Automata Theory蒋宗礼蒋宗礼11/20/12 2课程目的和基本要求课程目的和基本要求 课程性质课程性质 技术基础技术基础 基础知识要求基础知识要求 数学分析（或者高等数学），离散数学数学分析（或者高等数学），离散数学 主要特点主要特点 抽象和形式化抽象和形式化 理论证明和构造性理论证明和构造性 基本模型的建立与性质基本模型的建立与性质 11/20/12 3课程目的和基本要求课程目的和基本要求 本专业人员本专业人员 4 种基本的专业能力种基本的专业能力 计算思维能力计算思维能力

2、算法的设计与分析能力算法的设计与分析能力 程序设计和实现能力程序设计和实现能力 计算机软硬件系统的认知、分析、设计与应用能力计算机软硬件系统的认知、分析、设计与应用能力 计算思维能力计算思维能力 逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力 构造模型对问题进行形式化描述构造模型对问题进行形式化描述 理解和处理形式模型理解和处理形式模型11/20/12 4课程目的和基本要求课程目的和基本要求 知识知识 掌握正则语言、下文无关语言的文法、识别掌握正则语言、下文无关语言的文法、识别 模型及其基本性质、图灵机的基本知识。模型及其基本性质、图灵机的基本知识。 能力能力 培养学生的形式化描述和抽象

3、思维能力。培养学生的形式化描述和抽象思维能力。 使学生了解和初步掌握“问题、形式化描述使学生了解和初步掌握“问题、形式化描述 、自动化（计算机化）”这一最典型的计算、自动化（计算机化）”这一最典型的计算 机问题求解思路。 机问题求解思路。 11/20/12 5主要内容主要内容 语言的语言的文法文法描述。描述。 RL RG 、 、 FA 、 RE 、 RL 的性质的性质 。 。 CFL CFG(CNF 、 GNF) 、 PDA 、 CFL 的性质。的性质。 TM 基本基本 TM 、构造技术、构造技术、 TM 的修改。的修改。 CSL CSG 、 LBA 。11/20/12 6教材及主要参考书目教

4、材及主要参考书目1.1.蒋宗礼，姜守旭蒋宗礼，姜守旭 . 形式语言与自动机理论形式语言与自动机理论 . 北北 京：清华大学出版社，京：清华大学出版社， 2003 年年 2. John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 3. John E Hopcroft, Jeffrey D Ullman. Introduct

5、ion to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 197911/20/12 7第第 1 章章 绪论绪论1.1 集合的基础知识集合的基础知识 1.1.1 集合及其表示集合及其表示 集合：一定范围内的、确定的、并且彼此可集合：一定范围内的、确定的、并且彼此可 以区分的对象汇集在一起形成的整体叫做以区分的对象汇集在一起形成的整体叫做集集 合合 (set) ，简称为集，简称为集 (set) 。 元 素 ： 集 合 的 成 员 为 该 集 合 的元 素 ： 集 合 的 成 员 为

6、该 集 合 的 元 素元 素 (element) 。 集合描述形式。集合描述形式。 基数。基数。 集合的分类。集合的分类。 11/20/12 81.1.2 集合之间的关系集合之间的关系 子集子集 如果集合如果集合 A 中的每个元素都是集合中的每个元素都是集合 B 的元的元 素 ， 则 称 集 合素 ， 则 称 集 合 A 是 集 合是 集 合 B 的的 子 集子 集 (subset) ， 集 合， 集 合 B 是 集 合是 集 合 A 的的 包 集包 集 (container) 。 记 作。 记 作 A B 。 也 可 记 作。 也 可 记 作 B A 。 A B 读作集合读作集合 A 包含在

7、集合包含在集合 B 中中 ； B A 读作集合读作集合 B 包含集合包含集合 A 。 如果如果 A B ，且，且 xB ，但，但 x A ，则称，则称 A 是是 B 的的真子集真子集 (proper subset) ，记作，记作 A B 11/20/12 91.1.2 集合之间的关系集合之间的关系集合相等集合相等 如果集合如果集合 A ， B 含有的元素完全相同，则含有的元素完全相同，则 称集合称集合 A 与集合与集合 B 相等相等 (equivalence) ，记，记 作作 A=B 。 对任意集合对任意集合 A 、 B 、 C ： ： A=B iff A B 且且 B A 。 如果如果 A

8、B ，则，则 |A|B| 。 如果如果 A B ，则，则 |A|B| 。 如果如果 A 是有穷集，且是有穷集，且 A B ，则，则 |B| A| 。11/20/12 101.1.2 集合之间的关系集合之间的关系 如果如果 A B ，则对，则对 x A，有，有 x B。 如果如果 A B ，则对，则对 x A，有，有 x B并且并且 x B，但，但 x A 。 如果如果 A B 且且 B C ，则，则 A C 。 如 果如 果 A B 且且 B C ， 或 者， 或 者 A B 且且 B C ，或者，或者 A B 且且 B C ，则，则 A C 。 如果如果 A=B ，则，则 |A|=|B| 。

9、11/20/12 111.1.3 集合的运算集合的运算 并并 (union) A 与与 B 的的并并 (union) 是一个集合，该集合中的元是一个集合，该集合中的元 素要么是素要么是 A 的元素，要么是的元素，要么是 B 的元素，记作的元素，记作 AB 。 。 AB=a|aA 或者或者 aB A1A2An=a| i ， 1in ，使得，使得 aAi A1A2An =a| i ， iN, 使得使得 aAi=1iiA,|AaSAaASA=11/20/12 12交交 (intersection) 集合集合 A 和和 B 中都有的所有元素放在一起中都有的所有元素放在一起 构 成 的 集 合 为构 成

10、 的 集 合 为 A 与与 B 的的 交交 ， 记 作 ， 记 作 AB 。AB=a|aA 且且 aB “ ”“ ” 为 交 运 算 符 ，为 交 运 算 符 ， AB 读 作读 作 A 交交 B 。 。 如果如果 AB= ，则称，则称 A 与与 B 不相交。不相交。 AB= BA 。 (AB)C=A(BC) 。 AA=A 。11/20/12 13交交 (intersection) AB=A iff A B 。 。 A= 。 |AB|min|A| ， |B| 。 A(BC)=(AB)(AC)。 A(BC)=(AB)(AC)。 A(AB)=A。 A(AB)=A。11/20/12 14差差 (di

11、fference) 属于属于 A ，但不属于，但不属于 B 的所有元素组成的集合的所有元素组成的集合 叫做叫做 A 与与 B 的的差，记作差，记作 A-B 。 。 A-B=a|aA 且且 a B “-” 为减为减 ( 差差 ) 运算符，运算符， A-B 读作读作 A 减减 B 。 A-A=。 A-=A 。 A-B B-A 。 A-B=A iff AB= 。 A(B-C)=(AB)-(AC) 。 |A-B|A| 。11/20/12 15对称差对称差 (symmetric difference) 属于属于 A 但不属于但不属于 B ，属于，属于 B 但不属于但不属于 A 的的 所有元素组成的集合叫

12、所有元素组成的集合叫 A 与与 B 的的对称差，对称差， 记作记作 AB 。AB=a|aA 且且 a B 或者或者 a A 且且 aB “”“” 为对称差运算符。为对称差运算符。 AB 读作读作 A 对对 称减称减 B 。 。 AB=(AB)-(AB)=(A-B)(B-A) 。 。 11/20/12 16笛卡儿积笛卡儿积 (Cartesian product) A 与与 B 的的笛卡儿积笛卡儿积 (Cartesian product) 是一个是一个 集合，该集合是由所有这样的有序对集合，该集合是由所有这样的有序对 (a ， b) 组成的：其中组成的：其中 aA ， bB ，记作，记作 AB 。

13、AB=(a ， b)|aA对对 q Q2， a ， (q ， a)=2(q ， a) ； (f1， )=f ； (f2， )=f 。 。 11/20/12 3744.3.1 RE 到到 FA 的等价变换 的等价变换 n=k+1 r=r1+r2 11/20/12 3754.3.1 RE 到到 FA 的等价变换 的等价变换 M=(Q1Q2， ， q 01， f2) 对对 qQ1-f1 ， a (q ， a)=1(q ， a) ； 对对 qQ 2-f2 ， a (q ， a)=2(q ， a) ； (f1， )=q0211/20/12 3764.3.1 RE 到到 FA 的等价变换 的等价变换 r=

14、r1r2 11/20/12 3774.3.1 RE 到到 FA 的等价变换 的等价变换 M=(Q1q0， f ， ， q0， f) 其中其中 q0， f Q1，定义，定义 为为 对对 qQ1-f1 ， a ， (q ， a)=1(q ， a) 。 (f1， )=q01， f 。 (q0， )=q01， f 。11/20/12 3784.3.1 RE 到到 FA 的等价变换 的等价变换 r=r1* 11/20/12 3794.3.1 RE 到到 FA 的等价变换 的等价变换 按照定理按照定理 4-1 证明给出的方法构造一个证明给出的方法构造一个 给定给定 RE 的等价的等价 FA 时，该时，该 FA 有可能含有可能含 有许多的空移动。有许多的空移动。 可以按照自己对给定可以按照自己对给定 RE 的“理解”以的“理解”以 及对及对 FA 的 “理解” “直接地”构造出的 “理解” “直接地”构造出 一个比较“简单”的一个比较“简单”的 FA 。 定理证明中所给的方法是机械的。由于定理证明中所给的方法是机械的。由于 “直接地”构造出的“直接地”构造出的 FA 的正确性依赖的正确性