有限自动机理论CH1

《有限自动机理论CH1》由会员分享，可在线阅读，更多相关《有限自动机理论CH1（178页珍藏版）》请在金锄头文库上搜索。

1、有限自动机理论06016004陈文宇 电子科技大学计算机科学与工程学院联系方式 13808181782 B1-513 学时：（前8周）学分： 考试：闭卷、笔试 考查：作业(3-4次)，不参加考试教材：有限自动机理论陈文宇电子科技大学出版社 2007.3参考书形式语言与自动机理论(第2版) （蒋宗礼 姜守旭 清华大学出版社）形式语言与自动机（陈有祺 机械工业出版社）参考书Introduction to Automata Theory, Languages, and Computation (Second Edition)自动机理论、语言和计算导论 （John E. Hopcroft 清华大学出版

2、社）理论来源形式语言和自动机的理论来源于 (1) Chomsky对自然语言的研究； (2) ALGOL 60语言的语法描述方式； (3)Turing、Kleene、Neumann、 Huffman等 对自动机的研究。形式语言与自动机的作用形式语言和自动机的理论已经 成为计算机科学的理论基础。应用范围已被扩展到生物工程 、自动控制系统、图象处理与模 式识别等许多领域。计算机学科的专业能力计算思维能力算法设计与分析能力程序设计与实现能力计算机系统的认知、分析、设计和运用能力计算(机)思维能力形式化描述能力 抽象思维能力 逻辑思维方法相关理论是计算机学科基础。理论方面的知识是计算机科学的 真正灵魂。

3、这也是计算机科学与其他学科的 重要区别。有限自动机理论在科学领域中得 到直接应用对于计算机科学人才的计算思维 能力的培养，也具有重要作用。在本科阶段, 以观察、描述、比较分类、推断、应用 的科学思维过程为主。研究生阶段，需要进一步进行抽象 思维、逻辑思维、创造思维能力的 培养。本科生与研究生的根本区别在于研 究生的需要 宽厚、坚实的理论知识 。第1章 基础知识本章将对有限自动机理论中所需 的数学基础知识作扼要的介绍。包括集合及其运算、关系、证明 的方法、图与树的概念；以及一 些常用术语 和 形式语言与自动 机的发展 。内容：1.1集合及其运算1.2 关系1.3 证明和证明的方法1.4 图与树

4、1.5 语言1.6 常用术语 1.7 形式语言与自动机的发展 1.1 集合及其运算一些没有重复的对象的全体称为 集合，而这些被包含的对象称为 该集合的元素。集合中元素可以按任意的顺序进 行排列。使用大写英文字母表示一个集合 。有穷集合和无穷集合如果一个集合包含的元素个数是有 限的，称该集合为有穷集合。如果一个集合包含的元素是无限的 ，称该集合为无穷集合。无穷集合又分为可数集(如正奇数集) 和不可数集(如实数集)。集合的定义方法：列举法 命题法列举法(穷举法)对于有穷的，且元素个数较少的 集合，可以采用列举法，即将集 合的所有元素全部列出，并放在 一对花括号中。例 集合A =1，2，3，4，5对

5、于某些无穷集合，也可以使用类 似列举的方法进行描述如自然数集合：0，1，2，3，命题法对于集合元素较多的有穷集合或者是 无穷集合，可使用集合元素的形成模 式x | P(x)进行描述。 其中：x表示集合中的任一元素, P(x)是 一个谓词，对x进行限定。x | P(x) 表示 由满足P(x)的一切x构成的集合。可以使用自然语言，或者数学表 示法来描述谓词P(x)。例如：n | n是偶数 或n | n mod 2 = 0表明了由所有偶数组成的集合。集合的基数若集合A包含元素x，记为x A 反之， x A对于有穷集合A，使用|A|表示该集 合包含的元素的个数，也称基数 或势|A| = 0 A = 。

6、定义1-1 子集设A, B是两个集合，如果集合A中的 每个元素都是集合B的元素，则称集 合A是集合B的子集(集合B是集合A的 包集)A B 或 B AA, B是两个集合，如果A B，且x B，但x A，则称A是B的真子集A B两个集合相等，当且仅当A B且B A注意：不是A B且B A定义1-2 集合的运算集合A与集合B的并，记为AB。集合A的所有元素和集合B的所有 元素合并在一起组成的集合。AB=x | xA 或 xB 思考：什么情况下： AB=A ？集合A与集合B的交，记为AB是由集合A和集合B的所有公共元素 组成的集合。AB= x | xA 且 xB 思考：什么情况下： A B=A ？集

7、合A与集合B的差，记为AB属于集合A但不属于集合B的所有元 素组成的集合。AB= x |xA 且 x B 思考:什么情况下： A - B=A ？如果B A，将AB称为集合B（关 于集合A）的补。集合A称为集合B的全集（或论域）定义1-3 幂集设A为一个集合，那么A的幂 集为A的所有子集组成的集合记为2A2A=B | B A例1-1集合A=1，2，3，则A的幂集为:2A= ，1，2，3，1，2，1，3，2，3，1，2，3 幂集2A的元素个数当集合A为有穷集时，如果|A|=n ，那么A的幂集2A的元素个数(集 合A的所有子集的个数)为2n。（集合A的幂集表示为2A的原因 ）定义1-4 笛卡儿积集合

8、A和B的笛卡儿乘积A B（也简记为AB）A B = (a, b) |a A且b B当集合A、B为有穷集时|A B|= |A| *| B|例1-2设A = a, b, c, B = 0, 1,则A B =(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)B A=(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)也可根据约定记为：A B=a0, a1, b0, b1, c0, c1思考什么情况下： A B = B A ?练习110之间的和为10的整数 集合的集合 1, 9, 2, 8, 3, 7, 4, 6, 1,

9、 2, 7, 1, 3, 6, 1, 4, 5, 2, 3, 5, 1, 2, 3, 4注意：没有5，51.2 关系1.2.1 二元关系1.2.2 等价关系与等价类1.2.3 关系的合成1.2.1 二元关系设A和B为两个集合，则A B 的任何一个子集称为A到B的 一个二元关系。若R为A到B的关系，当(a, b) R时，可记为aRb。 若A = B ，则称为A上的关系。思考：如果集合A和B都是有穷集合，则A到B的二元关系有多少个？A到B的一个二元关系可以有多 少个元素？例1-3设A为正整数集合，则A上的关 系“0(5) 用AB代表集合A与B的连接A=a1,a2,a3,anB=b1,b2,b3,b

10、mAB= a1b1，a1b2，a1b3，a1bm，a2b1，a2b2，a2b3，a2bm，a3b1，a3b2，a3b3，a3bm，anb1，anb2，anb3，anbm 注意：A=A=一般，AB与BA是不相等的。思考:AB与BA在什么情况下相等? 1)当 A=B； 2)A或B中有一个为,则A=A=A 3)A和B中有一个为，则A=A=6)An代表集合A的n次连接(幂)A的n次幂定义为：(1) A0 = (2) An = An-1A n 17) A*代表A上所有字符串的集合即表示集合A中的所有字符串进 行任意次 连接而形成的串的集合A*称为集合A的闭包(克林闭包)A* = A0 A1 A2 An

11、例 A=0，1A0= 即长度为0的0和1组成的串的集 合 A1=A=0,1 即长度为1的0和1组成的串的集合A2=AA=00,01,10,11 即长度为2的0和1组成的串集合A3=A2A=000,001,010,011,100,101,110,111即长度为3的0和1组成的串的集合A* = A0 A1 A2 An =0和1 组成的所有的串=w|w是0和1 组成的串如果串是集合A的闭包中的串 ，也称是集合A上的串。 对于任何集合A有(A*)*= A*8) A+称为A的正闭包 A+=AA2A3An A * 与 A+A * = A+ A0 即A * = A+ 注意：A0= *=+=*=+=思考是否对

12、于任意的集合A，都有A+= A*-辨析与思考与|=1 |=0 A=A A= 9）给定字母表，则*的任意子 集L称为字母表上的一个语言 。本质上，语言L是字母表上的 字符串形成的集合。10)给定字母表， L是字母表 上的一个语言，是L的一 个字符串称为L的一个句子。串的长度|=0； |= n；若=a1a2a3an；其中：ai，n0； 11)前缀和后缀：x,y,z*，且x=yz y是x的前缀； 如果z ，则称y是x的真前缀； z是x的后缀； 如果y，则称z是x的真后缀；例1-13串abcde： 前缀：，a，ab，abc，abcd，abcde 真前缀：，a，ab，abc，abcd 后缀：，e，de，

13、cde，bcde，abcde 真后缀：，e，de，cde，bcde对于任意字符串x，x的前缀有|x|+1 个 真前缀有| x | 个对于任何字符串x，x的任意前缀y有 惟一的一个后缀z与之对应，使得 x=yz，反之亦然；对于任何字符串x，x的任意真前缀y 有惟一的一个真后缀z与之对应，使 得x=yz，反之亦然（除了以外）；对于任何字符串x x是自身的前缀，但不是真前缀 x是自身的后缀，但不是真后缀对于任何字符串x ， 是x的前缀，且是真前缀； 是x的后缀，且是真后缀；思考：对于，前缀是？真前缀？ 后缀是？真后缀？12)语言的前缀性质设L是某个字母表上的语言如果L中的任何句子都是另一个 句子的真

14、前缀，则称语言L具有 前缀性质。例1-14字母表0，1上的语言 L1=0n|n=0具有前缀性质； 语言L2=0n1|n=0不具有前缀性质。 语言与句子设是一个字母表，L *, L 称为字母表上的一个语言x L, x称为L的一个句子。语言的可分为有穷语言与无穷语 言语言的乘积设1, 2是两个字母表L1 1*, L2 2*, 语言L1与L2的乘积是一个语言：L1L2=xy | x L1, y L2该语言是字母表1 2 上的语言语言的例子字母表 0, 1上的一些语言：00, 110, 1, 00, 1100, 1*10, 1*1110, 1*语言的n次幂设是一个字母表，L *, L的n次幂是一个语言(1) 当n = 0时， Ln = (2) 当n 1时， Ln = Ln-1 L语言的例子令 = 0, 1，L = 0, 1L = 0, 1, 00, 01, 10, 11, = +L = , 0, 1, 00, 01, 10, 11, = *L = 0n1n | n 1L = 0n1m0k | n, m, k 1L = 0n1m0k | n, m, k 语言的闭包L的正闭包L+是一个语言：L+ = L L2 L3 L的克林闭包L*是一个语言：L* = L0 L+ 1.7形式语言与自动机的发展 l语言学家Chomsky(乔姆斯基)最早从产生 语言的角度研究语