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

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

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

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

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

5、数学系统，对其进行严格用数学方法将符号语言抽象成一个数学系统，对其进行严格 的形式化定义，并构建适当的描述模型，发展相关的知识和的形式化定义，并构建适当的描述模型，发展相关的知识和 理论，使之在科学实践中具有良好的指导作用。理论，使之在科学实践中具有良好的指导作用。 形式语言形式语言 形式语言与自动机理论的发展概况形式语言与自动机理论的发展概况 何为形式语言何为形式语言 形式语言的研究概况形式语言的研究概况 计算模型相关研究领域计算模型相关研究领域 数理语言学家致力于用数学方法研究数理语言学家致力于用数学方法研究自然语言自然语言的结构，试的结构，试 图用计算机模拟。图用计算机模拟。 研究概况研

6、究概况 1956年，宾夕法尼亚大学的语言学家年，宾夕法尼亚大学的语言学家 N. Chomsky 第一次第一次 提出用形式语言研究自然语言的方法。提出用形式语言研究自然语言的方法。 N. Chomsky 关于关于用形式文法派生语言的思路用形式文法派生语言的思路： 一组有限多个符号构成的集合一组有限多个符号构成的集合 ，称为字母表，称为字母表 ； 中所有符号串构成集合中所有符号串构成集合 *， * 每一个子集可视为每一个子集可视为 上的一个语言上的一个语言 L； 一个语言一个语言 L（所有句子）（所有句子） 可以按照文法可以按照文法 G L 的一系列描的一系列描 述规则（算法）形式化地派生出来。述

7、规则（算法）形式化地派生出来。 并给出了并给出了文法的乔姆斯基（文法的乔姆斯基（Chomsky）体系。）体系。 研究概况研究概况 0 型文法（短语结构文法或无限制文法）型文法（短语结构文法或无限制文法） 1 型文法（上下文有关文法）型文法（上下文有关文法） 2 型文法（上下文无关文法）型文法（上下文无关文法） 3 型文法（正则文法）型文法（正则文法） 派生符号语言的乔姆斯基（派生符号语言的乔姆斯基（Chomsky）文法体系：）文法体系： 研究概况研究概况 研究概况研究概况 1936年，英国数学家阿兰年，英国数学家阿兰.图灵图灵（A. M. Turing, 1912-1954）提出提出 一种抽象

8、计算模型一种抽象计算模型 图灵机图灵机( TM )，能根据，能根据内部状态，在一个无限内部状态，在一个无限 长磁带上进行读、写、移动等简单操作，计算所有可计算的函数；长磁带上进行读、写、移动等简单操作，计算所有可计算的函数； 是是模拟计算机算法的计算逻辑和研究可计算性的形式化描述工具。模拟计算机算法的计算逻辑和研究可计算性的形式化描述工具。 TM 的两个基本性质的两个基本性质: 计算对象能用有穷方式描述计算对象能用有穷方式描述; 计算过程必须由一系列离散的、可以机械执行的步骤组成。计算过程必须由一系列离散的、可以机械执行的步骤组成。 识别符号语言的识别符号语言的 A. Turing自动机体系：

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

10、立了确定有穷状态自动机时，基于图灵机建立了确定有穷状态自动机 DFA，用其，用其 识别语言；识别语言； 并证明并证明DFA与与RE的等价性。的等价性。 1957年，年，米凯尔米凯尔.拉宾拉宾 2、 a, b, c 0, 1 = a0, a1, b0, b1, 0c, c1 ; 3、 aa, ab, bb 0, 1 = aa0, aa1, ab0, ab1, bb0, bb1 字母表字母表与字符串与字符串 定义定义 1.3 设设是一个字母表，是一个字母表，的的 n 次幂可递归定义为：次幂可递归定义为： 0 = ; n = n-1, n1， 其中，其中，表示表示 由由 0 个字符（空字符）组成。个

11、字符（空字符）组成。 辨异辨异 - 与与 空集空集 的区别。的区别。 定义定义 1.4 设设是一个字母表，是一个字母表， 的正闭包：的正闭包： + = 2 3 . , 的克林闭包：的克林闭包： * = 0 2 3 . , 是是 上全体字符串构成的集合上全体字符串构成的集合 字母表字母表与字符串与字符串 例：例：1、 0, 1 + = 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 2、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 3、 a, b, c * = ,

12、 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 * = , a, b, c, aa, ab, ac, ba, bb, bc, , aaa, 3、 an = aaa 表示表示 n 个个 a 组成的字符串组成的字符串。 例：例： |

13、ab | = 2 , | aab | = 3, | an | = n , | a0 | = | = 0 定义定义 1.6： 设设是一个字母表，是一个字母表， x *，字符串字符串 x 中字符出现的总个中字符出现的总个 数叫做该串的长度，记作数叫做该串的长度，记作 | x |。 字母表与字母表与字符串字符串 定义定义 1.7： 设设 和和 是任意两个字符串，则是任意两个字符串，则 = 当且仅当当且仅当 | | = | |， 并且组成并且组成 的字符与组成的字符与组成 的字符依次对应相同。的字符依次对应相同。 例：例： 若若 = ab， = ab， 则则 = ； 若若 = ab， = ba， 则则

14、 。 字母表与字母表与字符串字符串 定义定义 1.8 ： 1、设、设 和和 是是 * 上任意的两个字符串，上任意的两个字符串， 和和 的连接构成的连接构成 一个新句子，记作一个新句子，记作 （简记为（简记为 ），），该句子由串该句子由串 后直接后直接 接串接串 组成。组成。 字母表与字母表与字符串字符串 2、对于、对于 n 0，字符串，字符串 的的 n 次幂为：次幂为： （1） 0 = ；（；（2） n = n-1 例：设例：设 = 0, 1 , x = 001, y = 1101； 1、 x0 = y0 =; 2、 xy = 0011101; 3、x2 = 001001 4、 y4 = 11

15、01110111011101, 字符串连接性质：字符串连接性质： 对于对于* 上任意字符串上任意字符串 x, y, z, 连接运算具有以下性质：连接运算具有以下性质： 1、结合律、结合律： ( xy ) z = x ( yz )。 2、左消去律：、左消去律： xy = xz y = z 。 3、右消去律：、右消去律： yx = zx y = z 。 4、唯一性：、唯一性： 存在唯一确定的存在唯一确定的 a1, a2, , an , 使得使得 x = a1a2 an。 5、单位元素：、单位元素： = = 字母表与字母表与字符串字符串 设设 是一个字母表，任意字符串是一个字母表，任意字符串 x ,

16、 y, z * ，且，且 x = yz， 则则 称称 y 是字符串是字符串 x 的前缀，的前缀，z 是是 x 的后缀；如果的后缀；如果 z ，则称，则称 y 是是 x 的真前缀；如果的真前缀；如果 y ，则称，则称 z 是是 x 的真后缀。的真后缀。 定义定义 1.9： 字母表与字母表与字符串字符串 例：例： 求求 = a, b 上字符串上字符串 abaabb 的前缀、后缀、真前缀、真后缀？的前缀、后缀、真前缀、真后缀？ 前缀：前缀： , a, ab, aba, abaa, abaab, abaabb 真前缀：真前缀： , a, ab, aba, abaa, abaab 后缀：后缀： , b,

17、 bb, abb, aabb, baabb, abaabb 真后缀：真后缀： , b, bb, abb, aabb, baabb 是每个字符串的前缀、后缀、子串。是每个字符串的前缀、后缀、子串。 定义定义1.10： 设设= a1 a2 an 是任意字符串，称字符串是任意字符串，称字符串 an a2 a1是是的逆，的逆， 记作记作T 若若 = T，则称则称为回文。为回文。 字母表与字母表与字符串字符串 例：设例：设 = abcd， T = dcba 例：字符串例：字符串 0110110 和和 deed 都是回文。都是回文。 定义定义 1.11： 设设是任意字母表，是任意字母表， L *， L 称

18、为字母表称为字母表上的一个上的一个 语言；语言； 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 1*， L2 2*，L1 和和 L2 的乘积的乘积 L1 L2= xy | x L1 y L2 是字母表是字母表

19、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？ 符号语言符号语言及其运算及其运算性质性质 定理定理 1.1 ：设：设 A、B、C、D 是是 上任意语言，有上任意语

20、言，有 1）A = A = 2）A = A = A 3）（AB）C = A（BC） 4）若）若 A B 和和 C D，有有 AC BD 5）A（B C）= AB AC 符号语言及其符号语言及其运算运算性质性质 - 摘自离散数学书版本1P145P145 6）（）（B C） A = B A C A 7） A（B C） A B A C 8）（）（B C）A B A C A 9） Am An = Am+n 10）（）（ Am ）n = Amn 11）若若 A B，则则 An Bn 符号语言及其符号语言及其运算运算性质性质 12）A* = A+ 13）An A*， 其中，其中，n 0 14） An A+

21、， 其中，其中，n 1 15） A A B 16） A B A 17）若若 A B，则则 A B 符号语言及其符号语言及其运算运算性质性质 18）若若 A B，则则 A+ B+ 19） AA* = A*A = A+ 20） 若若 A，则则 A = A+ 21）（A ） = A A = A 22）（A )* = （A+） = A 23）（A )+ = A+A+ = A+ 符号语言及其符号语言及其运算运算性质性质 例例1：（ R* ）* = R* 步骤步骤 1 ：求证有（求证有（ R* )n = R* ( n 1 )，施归纳于，施归纳于 R* 乘积的个数乘积的个数 n 基础语句基础语句： 设设 n = 1，（ R* )1 = R*，结论成立。，结论成立。 归纳语句归纳语句：设：设 n 1,（ R* )n = R* 结论成立，证结论成立，证 ( R* )n+1 = R* 时结论成立时结论成立 ( R* )n+1 = ( R*)n R* = R*R* 由归纳假设由归纳假设 = R R2 R3 R R2 R3 = R R2 R3 = R*