形式语言与自动机-2015-第01讲-概论

1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory教师：胡春明、赵永望、邓婷教师：胡春明、赵永望、邓婷课程定位：课程定位：揭示计算机科学与技术学科中计算的揭示计算机科学与技术学科中计算的本质问题本质问题 什么能且如何什么能且如何被（有效地）自动计算。被（有效地）自动计算。主要讨论计算机理论与应用中常用的各语言类对应的主要讨论计算机理论与应用中常用的各语言类对应的计算模型计算模型以及以及模型之间的联系与相互转换模型之间的联系与相互转换。形式语言与自动机形式语言与自动机课程目的：课程目的： 培养计算机科学方面的理论素养，提高逻辑思维和培养计算机

2、科学方面的理论素养，提高逻辑思维和解决相关问题的解决相关问题的能力，为今后从事科学研究或技术开发打下扎实的基础。能力，为今后从事科学研究或技术开发打下扎实的基础。教材教材: : 1 1、形式语言与自动机理论（第二版），蒋宗礼等，清华出版社，形式语言与自动机理论（第二版），蒋宗礼等，清华出版社，20072007参考教材：参考教材： 2、形式语言与自动机理论形式语言与自动机理论”，吴哲辉等编著，机械工业出版社，吴哲辉等编著，机械工业出版社，2008 “自动机理论、语言和计算导论自动机理论、语言和计算导论”，孙家啸等译，机械工业出版社，孙家啸等译，机械工业出版社形式语言与自动机形式语言与自动机前续课

3、程：前续课程： 离散数学离散数学 数理逻辑、集合论等数理逻辑、集合论等MOOCMOOC素材素材: : 1 1、自动机、自动机(Automate(Automate），斯坦福大学），斯坦福大学CS154CS154 http:/ 形式语言与自动机形式语言与自动机形式文法与自动机理论的发展概况形式文法与自动机理论的发展概况学习意义与课程特点学习意义与课程特点课程教学内容与前期准备课程教学内容与前期准备符号语言符号语言第一章第一章 课程概述及预备知识课程概述及预备知识形式语言与自动机理论的发展概况形式语言与自动机理论的发展概况何为形式语言何为形式语言形式语言的研究概况形式语言的研究概况计算模型相关研究领

4、域计算模型相关研究领域何为何为“语言语言”：斯大林斯大林 语言是人们所理解的字和组合这些字的方法。语言是人们所理解的字和组合这些字的方法。韦波斯特韦波斯特 语言是为大范围人群懂得、并能使用的字符以语言是为大范围人群懂得、并能使用的字符以及组合这些字符的方法的一个统一体。及组合这些字符的方法的一个统一体。形式语言形式语言语言：语言：自然语言（自然语言（ 英语、汉语）、英语、汉语）、 符号语言（符号语言（ 程序设计语言、标记语言、算法程序设计语言、标记语言、算法 等）等）形式语言形式语言 元语言：元语言：用数学方法将符号语言抽象成一个数学系统，对其进行严格用数学方法将符号语言抽象成一个数学系统，对

5、其进行严格的形式化定义，并构建适当的描述模型，发展相关的知识和的形式化定义，并构建适当的描述模型，发展相关的知识和理论，使之在科学实践中具有良好的指导作用。理论，使之在科学实践中具有良好的指导作用。形式语言形式语言形式语言与自动机理论的发展概况形式语言与自动机理论的发展概况何为形式语言何为形式语言形式语言的研究概况形式语言的研究概况计算模型相关研究领域计算模型相关研究领域 数理语言学家致力于用数学方法研究数理语言学家致力于用数学方法研究自然语言自然语言的结构，试的结构，试图用计算机模拟。图用计算机模拟。研究概况研究概况 1956年，宾夕法尼亚大学的语言学家年，宾夕法尼亚大学的语言学家 N. C

6、homsky 第一次第一次提出用形式语言研究自然语言的方法。提出用形式语言研究自然语言的方法。N. Chomsky 关于关于用形式文法派生语言的思路用形式文法派生语言的思路： 一组有限多个符号构成的集合一组有限多个符号构成的集合 ，称为字母表，称为字母表 ； 中所有符号串构成集合中所有符号串构成集合 *， * 每一个子集可视为每一个子集可视为上的一个语言上的一个语言 L； 一个语言一个语言 L（所有句子）（所有句子） 可以按照文法可以按照文法 G L 的一系列描的一系列描述规则（算法）形式化地派生出来。述规则（算法）形式化地派生出来。并给出了并给出了文法的乔姆斯基（文法的乔姆斯基（Chomsk

7、y）体系。）体系。研究概况研究概况0 型文法（短语结构文法或无限制文法）型文法（短语结构文法或无限制文法）1 型文法（上下文有关文法）型文法（上下文有关文法）2 型文法（上下文无关文法）型文法（上下文无关文法） 3 型文法（正则文法）型文法（正则文法）派生符号语言的乔姆斯基（派生符号语言的乔姆斯基（Chomsky）文法体系：）文法体系：研究概况研究概况研究概况研究概况 1936年，英国数学家阿兰年，英国数学家阿兰.图灵图灵（A. M. Turing, 1912-1954）提出提出一种抽象计算模型一种抽象计算模型 图灵机图灵机( TM )，能根据，能根据内部状态，在一个无限内部状态，在一个无限长

8、磁带上进行读、写、移动等简单操作，计算所有可计算的函数；长磁带上进行读、写、移动等简单操作，计算所有可计算的函数；是是模拟计算机算法的计算逻辑和研究可计算性的形式化描述工具。模拟计算机算法的计算逻辑和研究可计算性的形式化描述工具。 TM 的两个基本性质的两个基本性质: 计算对象能用有穷方式描述计算对象能用有穷方式描述; 计算过程必须由一系列离散的、可以机械执行的步骤组成。计算过程必须由一系列离散的、可以机械执行的步骤组成。识别符号语言的识别符号语言的 A. Turing自动机体系：自动机体系：基本的图灵机模型的物理装置：基本的图灵机模型的物理装置：控制器：左右移动、读字符、修改方格字符、改变控

9、制器状态控制器：左右移动、读字符、修改方格字符、改变控制器状态 ； 模拟计算机的基本操作。模拟计算机的基本操作。装置改进：装置改进：单带多道；子程序功能；单带无穷；多带；多维；通用 TM。研究概况研究概况研究概况研究概况1943年，年，McCulloch-Pitts神经模型：莫克罗神经模型：莫克罗（WSMcCulloch）和彼特（）和彼特（WPitts）1951- 1956年，数学家克林（年，数学家克林（Kleene）：研究神经细胞）：研究神经细胞时，基于图灵机建立了确定有穷状态自动机时，基于图灵机建立了确定有穷状态自动机 DFA，用其，用其识别语言；识别语言； 并证明并证明DFA与与RE的等

10、价性。的等价性。 1957年，年，米凯尔米凯尔.拉宾拉宾 & 达纳达纳.斯科特斯科特（Dana Stewart Scott，1976年图灵奖年图灵奖）将确定状态自动机）将确定状态自动机 DFA 扩展为扩展为非确定有穷状态自动机非确定有穷状态自动机 NFA，从而，从而简化了机器的描述建简化了机器的描述建模过程，提高了解题（识别语言）速度，模过程，提高了解题（识别语言）速度，为其在机器翻为其在机器翻译、文献检索的语言识别及符号处理等中的应用奠定了译、文献检索的语言识别及符号处理等中的应用奠定了基础。基础。识别符号语言的识别符号语言的 A. Turing 自动机体系：自动机体系：问题：问题：给定的给

11、定的形式文法形式文法和和自动机自动机描述的是否是同一符号语言；两种形式化描述的是否是同一符号语言；两种形式化方法是否等价；如何证明？二者能否在等价基础上相互模拟与转换？方法是否等价；如何证明？二者能否在等价基础上相互模拟与转换？如何证明这种转换的正确性？如何实现转换的形式化和自动化，即，如何证明这种转换的正确性？如何实现转换的形式化和自动化，即，是否能用计算机的算法实现？是否能用计算机的算法实现？ 1959年，年，N.乔姆斯基发现：文法和自动机分别从派生和识别角度乔姆斯基发现：文法和自动机分别从派生和识别角度表达语言，并证明文法和自动机的等价性，开启了用数学方法研表达语言，并证明文法和自动机的

12、等价性，开启了用数学方法研究形式语言的先河。究形式语言的先河。研究概况研究概况0 型文法（无限制文法）型文法（无限制文法） 图灵机图灵机 1 型文法（上下文有关文法）型文法（上下文有关文法） 线性有界自动机线性有界自动机 2 型文法（上下文无关文法）型文法（上下文无关文法） 下推自动机下推自动机 3 型文法（正则文法）型文法（正则文法） 有穷状态自动机有穷状态自动机 两种计算模型的对应关系：两种计算模型的对应关系：研究概况研究概况1977 Amir Pnueli.将自动机与逻辑建立关系，基于此发展将自动机与逻辑建立关系，基于此发展了模型检测技术了模型检测技术 * 判定性、复杂性、表达能力判定性

13、、复杂性、表达能力研究概况研究概况形式语言与自动机理论的发展概况形式语言与自动机理论的发展概况何为形式语言何为形式语言形式语言的研究概况形式语言的研究概况计算模型相关研究领域计算模型相关研究领域计算模型相关研究领域计算模型相关研究领域1 1、可计算性问题的提出：、可计算性问题的提出：希尔伯特（希尔伯特（D. Hilbert, 1862-1943D. Hilbert, 1862-1943）纲领）纲领 是否对各个数学分支都能建立一套形式化的公理系统，使得所涉及领域是否对各个数学分支都能建立一套形式化的公理系统，使得所涉及领域内的任何命题，都可通过系统的有限步推导，判断命题是否正确。内的任何命题，都

14、可通过系统的有限步推导，判断命题是否正确。2 2、存在不可判定命题：、存在不可判定命题：歌德尔（歌德尔（K. Godel, 1906-1978K. Godel, 1906-1978） 在包含初等数论的协调的形式系统中，存在不可判定问题；即，存在包含初等数论的协调的形式系统中，存在不可判定问题；即，存在一个命题在一个命题 A A，无法在该系统内证明，无法在该系统内证明 A A 或或 A A 为真。为真。3 3、可计算问题转换为：、可计算问题转换为： 是否存在这样一种抽象的形式系统，它可以衡量什么问题是可以判定是否存在这样一种抽象的形式系统，它可以衡量什么问题是可以判定（可计算）的，什么问题是不可

15、判定（不可计算）的。（可计算）的，什么问题是不可判定（不可计算）的。若干可计算模型：若干可计算模型：1 1、英国数学家图灵、英国数学家图灵 1936 1936 年提出图灵机年提出图灵机 2 2、赫尔布拉德、赫尔布拉德(1932)(1932)、哥德尔（、哥德尔（19361936）、克林尼（）、克林尼（19361936）提出一般递归函数）提出一般递归函数 3 3、邱奇（、邱奇（1933-1935 1933-1935 ）提出）提出 - - 演算演算 成果：成果：1 1、邱奇证明：一般递归函数、邱奇证明：一般递归函数 同同 - - 可定义的等价性；可定义的等价性；2 2、克林尼证明：图灵可计算、克林尼

16、证明：图灵可计算 同同 - - 可定义的等价性；可定义的等价性；邱奇邱奇 - - 图灵论题：图灵论题：一个函数是可计算的当且仅当它是图灵机可计算的一个函数是可计算的当且仅当它是图灵机可计算的（或（或 - - 可定义的）。可定义的）。计算模型的相关研究领域计算模型的相关研究领域形式文法与自动机理论的发展概况形式文法与自动机理论的发展概况学习意义与课程特点学习意义与课程特点课程教学内容与前期准备课程教学内容与前期准备符号语言符号语言第一章第一章 课程概述及预备知识课程概述及预备知识一、深化计算机基础理论学习：一、深化计算机基础理论学习： 1、形式语言形式语言为计算机程序语言编译过程提供了理论基础；

17、 3、有限状态自动机有限状态自动机为数字逻辑电路等设计提供了描述手段； 2、图灵机模型图灵机模型为计算机的计算理论提供了模型基础。学习意义学习意义与课程特点与课程特点三、人才培养：三、人才培养： 形式语言与自动机理论对于计算机领域人才的计算思维能力的培养起到至关重要的作用。二、应用拓展：二、应用拓展： 1、在人工智能的自然语言理解与翻译、WEB服务标注语言词法及语法结构与模式识别等方面有着广泛的应用。 2、为操作系统的状态变换，网络状态描述等各种模型系统的建模提供方法。学习意义学习意义与课程特点与课程特点“计算思维能力计算思维能力”梯级式训练过程：梯级式训练过程：学习意义学习意义与课程特点与课

18、程特点本课程强调：本课程强调：1、抽象性：抽象性：形式语言研究如何利用数学方法抽象出符号语言的结构特征及相关的文法规则；自动机理论研究各种能自动处理符号串的计算模型；二者描述的理论基础是离散数学，内容具有一定抽象性。2、构造性：构造性：课程包含大量的构造性内容，如给定语言构造生成语言的形式文法或识别语言的自动机；给定文法构造等价的自动机等3、理论性：理论性：形式语言与自动机理论的大部分内容属于理论形态，拥有完整的理论体系；包含许多定义、定理及其相关的递归证明。学习意义与学习意义与课程特点课程特点形式文法与自动机理论的发展概况形式文法与自动机理论的发展概况学习意义与课程特点学习意义与课程特点课程

19、教学内容与前期准备课程教学内容与前期准备符号语言符号语言第一章第一章 课程概述及预备知识课程概述及预备知识第四章第四章 正则表达式以及其与文法、自动机的等价性正则表达式以及其与文法、自动机的等价性第三章第三章 各种有限状态自动机及其相互等价性各种有限状态自动机及其相互等价性第五章第五章 正则语言的性质正则语言的性质第六章第六章 上下文无关文法上下文无关文法第二章第二章 形式文法形式文法28第一章第一章 课程概述及预备知识课程概述及预备知识课程教学内容课程教学内容第七章第七章 下推自动机下推自动机以及其与上下文无关文法的等价性以及其与上下文无关文法的等价性第八章第八章 图灵机初步图灵机初步第九章

20、第九章 案例分析（语言验证、自然语言理解、案例分析（语言验证、自然语言理解、状态跟踪等）状态跟踪等）课程前期准备课程前期准备 集合与归纳证明集合与归纳证明v集合的表示集合的表示： 列举法、命题法列举法、命题法v集合的基数（势）集合的基数（势）：有穷集合、可数无穷集合、不可数无穷集合有穷集合、可数无穷集合、不可数无穷集合v集合关系的定义集合关系的定义： A B 、 A = B、 v集合的运算集合的运算： A B、A B、A B、A B、 A、(A ) = 2A、v二元关系二元关系： 有序偶集合有序偶集合v关系的性质关系的性质： 自反性、反自反性、对称性、反对称性、传递性自反性、反自反性、对称性、

21、反对称性、传递性v等价关系等价关系： 具有自反、对称、传递性质的关系具有自反、对称、传递性质的关系v等价划分与等价类等价划分与等价类： 用等价关系用等价关系R对集合对集合 S 进行的划分进行的划分, 每个子集每个子集 Si 为一个等价类为一个等价类v关系的合成与闭包关系的合成与闭包： 正闭包，记为正闭包，记为 “ R+ ” - 满足满足 “传递传递” 性质；性质； 克林闭包，记为克林闭包，记为 “ R* ” - 满足满足 “自反、传递自反、传递” 性质性质v递归定义递归定义： 构造无穷集合；构造无穷集合； v归纳证明归纳证明： 证明无穷集合元素均具有证明无穷集合元素均具有 P 性质性质形式语言

22、与自动机理论的发展概况形式语言与自动机理论的发展概况学习意义课程特点学习意义课程特点课程教学内容与前期准备课程教学内容与前期准备符号语言符号语言第一章第一章 课程概述及预备知识课程概述及预备知识定义定义 1.1 字母表是一个字母表是一个非空有限非空有限集合，通常记作集合，通常记作，其中元素称为，其中元素称为字母表的字符。字母表的字符。字母表及其字符特点：字母表及其字符特点： 1 1、字母表具有非空、有穷性；字母表具有非空、有穷性； 2 2、字符具有不可分性、整体性；字符具有不可分性、整体性； 3 3、字符具有可区分性字符具有可区分性 、可辨认性。、可辨认性。字母表字母表与字符串与字符串例：考察

23、以下字母表：例：考察以下字母表： 1 = aa, ab, bb ； 2 = a, a, b, b ； 3 = a, b, a 。字母表字母表与字符串与字符串定义定义 1.2 设设1，2 是两个字母表，是两个字母表，1，2 的乘积定义为的乘积定义为12 = ab | a 1 b 2 。例：例： 1、 0, 1 a, b, c = 0a, 0b, 0c, 1a, 1b, 1c ; 2、 a, b, c 0, 1 = a0, a1, b0, b1, 0c, c1 ; 3、 aa, ab, bb 0, 1 = aa0, aa1, ab0, ab1, bb0, bb1 字母表字母表与字符串与字符串定义定

24、义 1.3 设设是一个字母表，是一个字母表，的的 n 次幂可递归定义为：次幂可递归定义为： 0 = ; n = n-1, n1， 其中，其中，表示表示 由由 0 个字符（空字符）组成。个字符（空字符）组成。辨异辨异 - 与与 空集空集 的区别。的区别。定义定义 1.4 设设是一个字母表，是一个字母表， 的正闭包：的正闭包： + = 2 3 . , 的克林闭包：的克林闭包： * = 0 2 3 . , 是是 上全体字符串构成的集合上全体字符串构成的集合字母表字母表与字符串与字符串例：例：1、 0, 1 + = 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 1

25、00, . ; 2、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 3、 a, b, c * = , a, b, c, aa, ab, ac, ba, bb, bc, , aaa, 字母表与字母表与字符串字符串定义定义 1.5 设设是一个字母表，是一个字母表， x *， x 叫做叫做 上的一个句子（上的一个句子（字符串、符号串）。字符串、符号串）。例：例： 1、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 2、 a, b, c * = ,

26、 a, b, c, aa, ab, ac, ba, bb, bc, , aaa, 3、 an = aaa 表示表示 n 个个 a 组成的字符串组成的字符串。 例：例： | ab | = 2 , | aab | = 3, | an | = n , | a0 | = | = 0定义定义 1.6： 设设是一个字母表，是一个字母表， x *，字符串字符串 x 中字符出现的总个中字符出现的总个数叫做该串的长度，记作数叫做该串的长度，记作 | x |。字母表与字母表与字符串字符串定义定义 1.7： 设设 和和 是任意两个字符串，则是任意两个字符串，则 = 当且仅当当且仅当 | | = | |，并且组成并且

27、组成 的字符与组成的字符与组成 的字符依次对应相同。的字符依次对应相同。 例：例： 若若 = ab， = ab， 则则 = ； 若若 = ab， = ba， 则则 。 字母表与字母表与字符串字符串定义定义 1.8 ： 1、设、设 和和 是是 * 上任意的两个字符串，上任意的两个字符串， 和和 的连接构成的连接构成一个新句子，记作一个新句子，记作 （简记为（简记为 ），），该句子由串该句子由串 后直接后直接接串接串 组成。组成。字母表与字母表与字符串字符串 2、对于、对于 n 0，字符串，字符串 的的 n 次幂为：次幂为： （1） 0 = ；（；（2） n = n-1 例：设例：设 = 0, 1

28、 , x = 001, y = 1101； 1、 x0 = y0 =; 2、 xy = 0011101; 3、x2 = 001001 4、 y4 = 1101110111011101,字符串连接性质：字符串连接性质：对于对于* 上任意字符串上任意字符串 x, y, z, 连接运算具有以下性质：连接运算具有以下性质： 1、结合律、结合律： ( xy ) z = x ( yz )。 2、左消去律：、左消去律： xy = xz y = z 。 3、右消去律：、右消去律： yx = zx y = z 。 4、唯一性：、唯一性： 存在唯一确定的存在唯一确定的 a1, a2, , an , 使得使得 x

29、= a1a2 an。 5、单位元素：、单位元素： = = 字母表与字母表与字符串字符串 设设 是一个字母表，任意字符串是一个字母表，任意字符串 x , y, z * ，且，且 x = yz， 则则称称 y 是字符串是字符串 x 的前缀，的前缀，z 是是 x 的后缀；如果的后缀；如果 z ，则称，则称 y 是是 x 的真前缀；如果的真前缀；如果 y ，则称，则称 z 是是 x 的真后缀。的真后缀。定义定义 1.9： 字母表与字母表与字符串字符串例：例： 求求 = a, b 上字符串上字符串 abaabb 的前缀、后缀、真前缀、真后缀？的前缀、后缀、真前缀、真后缀？前缀：前缀： , a, ab,

30、aba, abaa, abaab, abaabb真前缀：真前缀： , a, ab, aba, abaa, abaab后缀：后缀： , b, bb, abb, aabb, baabb, abaabb真后缀：真后缀： , b, bb, abb, aabb, baabb是每个字符串的前缀、后缀、子串。是每个字符串的前缀、后缀、子串。定义定义1.10： 设设= a1 a2 an 是任意字符串，称字符串是任意字符串，称字符串 an a2 a1是是的逆，的逆，记作记作T 若若 = T，则称则称为回文。为回文。字母表与字母表与字符串字符串例：设例：设 = abcd， T = dcba例：字符串例：字符串 0

31、110110 和和 deed 都是回文。都是回文。定义定义 1.11： 设设是任意字母表，是任意字母表， L *， L 称为字母表称为字母表上的一个上的一个语言；语言； x L， x 叫做叫做 L 的一个句子。的一个句子。符号语言符号语言及其运算性质及其运算性质例：设例：设 = 0, 1 , 可定义可定义 上的不同语言如下：上的不同语言如下： 1、 0, 1 ; 00, 11 ; 0, 1, 00, 11, 01, 10 ; 2、 0, 1 *; 00, 11 *; 0, 1, 00, 11, 01, 10 *; 定义定义 1.12 1.12 ：设设 1 和和 2 是字母表，是字母表， L1

32、1*， L2 2*，L1 和和 L2 的乘积的乘积 L1 L2= xy | x L1 y L2 是字母表是字母表 1 2 上的一个语言。上的一个语言。例例: 设设 L1 = ab，ac , L2 = e，bc , 有有 L1L2 = abe，abbc， ace，acbc 。符号语言符号语言及其运算及其运算性质性质例：设例：设 = 0, 1 , 分析下列语言的结构特征及其关系。分析下列语言的结构特征及其关系。1、有穷语言有穷语言 ？无穷语言？无穷语言 ?2、L5L7 = L6 ？ L5L7 = L8 ？ L9 = L10 ？3、 L6 L5L7 ？ L9 L10 ？ L6 L11？符号语言符号语

33、言及其运算及其运算性质性质定理定理 1.1 ：设：设 A、B、C、D 是是 上任意语言，有上任意语言，有 1）A = A = 2）A = A = A 3）（AB）C = A（BC）4）若）若 A B 和和 C D，有有 AC BD5）A（B C）= AB AC符号语言及其符号语言及其运算运算性质性质 - 摘自离散数学书版本1P145P1456）（）（B C） A = B A C A7） A（B C） A B A C8）（）（B C）A B A C A9） Am An = Am+n10）（）（ Am ）n = Amn 11）若若 A B，则则 An Bn 符号语言及其符号语言及其运算运算性质性质 12）A* = A+ 13）An A*， 其中，其中，n 0 14） An A+， 其中，其中，n 1 15） A A B 16） A B A 17）若若 A B，则则 A B 符号语言及