形式语言与自动机理论一精.pptx

《形式语言与自动机理论一精.pptx》由会员分享，可在线阅读，更多相关《形式语言与自动机理论一精.pptx（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、参考教材参考教材1、形式语言与自动机理论 作者：蒋宗礼、姜守旭 出版社：清华大学出版社 2、An Introduction to Formal Languages and Automata(Third Edition)作者：Peter Linz 出版社：机械工业出版社3、Introduction to Automata Theory,Languages,and Computation (Second Edition)作者：John E.Hopcroft,Rajeev Motwani,Jeffrey D.Ullman 出版社：清华大学出版社第1页/共73页第一章第一章 绪论绪论计算机科学研究的课

2、题是：可计算性；算法和复杂性理论；数据结构和数据库；人工智能；人机交互和人机界面。第2页/共73页第一章第一章 绪论绪论计算机科学理论计算机科学 自动机论与形式语言理论；程序理论（包括程序正确性证明、程序验证等）；形式语义学；算法分析和计算复杂性理论。实验计算机科学 第3页/共73页第一章第一章 绪论绪论1.4 语言Webster 定义：为相当大的团体的人所懂得,并使的字和组合这些字的方法的统一体。第4页/共73页第一章第一章 绪论绪论1.4 语言吴天蔚 定义：语言可以被看成一个抽象的数学系统。（1994）(信息产业部计算机与微电子发展研究中心)Chomsky 定义：按照一定规律构成的句子和符

3、号串的有限或无限的集合。第5页/共73页第一章第一章 绪论绪论1.4 语言 （1）产生过程n 形式语言的产生过程n 自动机的产生过程（2）作用第6页/共73页第一章第一章 绪论绪论1.4 语言 形式语言的直观意义 形式语言是用来精确描述语言（包括人工语言和自然语言）及其结构的手段。形式语言学也称代数语言学。第7页/共73页第一章第一章 绪论绪论1.4 语言 对语言研究的主要方面：（2）有穷描述（1）表示（3）语言的结构第8页/共73页第一章第一章 绪论绪论语言描述的三种途径：（1）穷举法：只适合句子数目有效的语言。（2）语法描述：生成语言中合格的句子。（3）自动机：对输入的句子进行检验，区别哪

4、些是语言中的句子，哪些不是语言中的句子。1.4 语言第9页/共73页第一章第一章 绪论绪论1.4 语言（1）符号（2）字母表 （3）字符串（4）语言字母表的运算乘积运算幂运算闭包运算第10页/共73页第二章第二章 文法文法2.1 文法的引入例1 1 汉语中的句子：王平和李新是大学生。它由两个短语组成：主语谓语王平和李新是大学生 该句子可以应用下列规则构成：第11页/共73页第二章第二章 文法文法1句子主语谓语2主语名词短语3名词短语名词4名词短语名词连接词名词短语5.名词王平6.名词李新7.连词和8.谓语动宾短语9动宾短语动词宾语10.动词是11.宾语名词12.名词大学生 第12页/共73页第

5、二章第二章 文法文法该文法也能产生:王平是大学生；李新和王平是大学生；王平和大学生是李新；王平和王平和王平是王平 等句子。第13页/共73页第二章第二章 文法文法2.2 文法的形式定义 文法 G 是一个4元组 G=(V,T,P,S)其中：（1）V 是非终结符非空有限集合；（2）T 是终结符的非空有限集合；并且V T=F；（3）P 是产生式的非空有限集合；（4）S V 是文法G的开始符。第14页/共73页第二章第二章 文法文法2.2 文法的形式定义定义：假设 G=(V,T,P,S)是一个文法。如果 a b P,并且,(VT）*，则称 a 直接推导出 b，记为：a b 如果 a b，则称 b 在文

6、法G中直接归约成a，简称为归约。第15页/共73页第二章第二章 文法文法2.2 文法的形式定义定义：设文法 G=(V,T,P,S)。对(VT)*，如果S()*,则为文法G的一个句型；若对wT*，如果 S()*w，则 w 称为由 G产生的一个句子。称 L(G)=w|w T*,S()*w为文法 G 产生的语言。第16页/共73页第二章第二章 文法文法2.3 文法的构造例1：构造文法 G，使 L(G)=0,1,00,11定义：假设 G1,G2 是文法，如果 L(G1)=L(G2)，则称 G1,G2 是等价的。第17页/共73页第二章第二章 文法文法2.3 文法的构造例2：构造文法 G，使(1)L(G

7、)=0n|n0(2)L(G)=0n|n1(3)L(G)=0n1n|n0(4)L(G)=0n1n|n1(5)L(G)=0n1n+1|n0(6)L(G)=0n1n2n|n1第18页/共73页第二章第二章 文法文法2.4 文法的类型Chomsky 体系(1)0 型文法(短语结构文法)对产生式不做任何限制 PSG(phrase structure grammar)PSL(phrase structure language)RE (recursively enumerable)第19页/共73页第二章第二章 文法文法2.4 文法的类型Chomsky 体系(2)1 型文法（上下文有关文法）对P,都有|CS

8、G(context sensitive grammar)CSL(context sensitive language)第20页/共73页第二章第二章 文法文法2.4 文法的类型Chomsky 体系(3)2 型文法（上下文无关文法）对P,都有|，并且V CFG(context free grammar)CFL(context free language)第21页/共73页第二章第二章 文法文法2.4 文法的类型Chomsky 体系(4)3 型文法（正规文法、正则文法）对P,有以下形式：AwB,Aw or ABw,Aw 其中 A,BV,wT+RG(regular grammar)RL(regula

9、r language)第22页/共73页第二章第二章 文法文法2.4 文法的类型定理：L 是 RL 的充分必要条件是存在一个文法，该文法产生语言L,并且产生式的形式是：AaB,Aa or ABa,Aa 其中 A,BV,aT.第23页/共73页第二章第二章 文法文法2.4 文法的类型2.5 空语句定义：假设G=(V,T,P,S)是一个文法。如果 S 不出现在 G 的任何产生式的右部，则PS所形成的文法仍然是与G等价的相应类型的文法，所产生的语言是相应类型的语言。第24页/共73页第三章第三章 有限状态自动机有限状态自动机3.1 有限状态系统3.2 有限状态自动机的形式定义（）形式定义定义：有限状

10、态自动机（finite automaton,FA）是一个五元组：=(Q,q0,F)其中，Q：非空有限状态集合；：有限输入字母表；：状态转换函数；：QQ；（DFA）q0：q0Q,是的初始状态；F：FQ 是的终止状态集。第25页/共73页第三章第三章 有限状态自动机有限状态自动机3.1 有限状态系统3.2 有限状态自动机的形式定义例如：假设DFA M=(Q,q0,F)。其中Q=q0,q1,q2,q3，=a,b，F=q3第26页/共73页第三章第三章 有限状态自动机有限状态自动机3.1 有限状态系统3.2 有限状态自动机的形式定义输入字符串时，转换函数为：其定义为：对(1)对，有(2)当时，第27页

11、/共73页第三章 有限状态自动机3.2 有限状态自动机的形式定义（）设计有限状态自动机例：构造一台有限状态自动机，它能够识别所有由奇数个和奇数个组成的字符串。设计 考虑有以下状态：（1）到此为止读入偶数个 a 和偶数个 b;（2）到此为止读入奇数个 a 和偶数个 b;（3）到此为止读入偶数个 a 和奇数个 b;（4）到此为止读入奇数个 a 和奇数个 b;第28页/共73页例：设计一台有限状态自动机，识别含有00 作为子串的所有0,1上的字符串组成的语言。设计 考虑以下状态：（1）开始状态，什么都没有输入或者输入 1；（2）接收到的符号是 0；（3）接收到的符号是 00；第三章 有限状态自动机3

12、.2 有限状态自动机的形式定义（）设计有限状态自动机第29页/共73页第三章 有限状态自动机3.2 有限状态自动机的形式定义（）设计有限状态自动机例3：设计一个DFA M，它能识别所有能被 3 整除的十进制数。设计 可以考虑有以下情况：（1）已输入的数字与上一余数之和被 3 除余 0；（2）已输入的数字与上一余数之和被 3 除余 1；（3）已输入的数字与上一余数之和被 3 除余 2；第30页/共73页第三章第三章 有限状态自动机有限状态自动机3.2 有限状态自动机的形式定义（3）即时描述（瞬时描述、格局）定义：设 M=(Q,q0,F)是一个FA,x,y*,(q0,x)=q。则 xqy 称为 M

13、 的一个即时描述 (instantaneous description,ID)。第31页/共73页第三章第三章 有限状态自动机有限状态自动机3.2 有限状态自动机的形式定义（4）到达某状态的字符串集合定义：设 FA M=(Q,q0,F)，对 qQ 能从开始状态到达所输 入的字符串集合为：set(q)=x|x*,并且(q0,x)=q第32页/共73页第三章第三章 有限状态自动机有限状态自动机3.2 有限状态自动机的形式定义（5）有限状态自动机等价 假设 M1,M2 是 FA，如果 L(M1)=L(M2)，则 M1 与 M2 等价。第33页/共73页第三章第三章 有限状态自动机有限状态自动机3.3

14、 非确定的有限自动机(NFA)（1）形式定义定义：非确定有限自动机（non-deterministic finite automaton,NFA）是一个五元组：=(Q,q0,F)其中，Q、q0、F的定义与在FA中的定义相同；：状态转换函数，：Qp(Q)即对(q,a)Q (q,a)=p1,p2,pmQ第34页/共73页第三章第三章 有限状态自动机有限状态自动机3.3 非确定的有限自动机(NFA)状态转换函数 ：Qp(Q)，对qQ对*对a,w*有对PQ第35页/共73页第三章第三章 有限状态自动机有限状态自动机3.3 非确定的有限自动机(NFA)（1）形式定义 非确定的有限自动机(NFA M)所接

15、受的语言:第36页/共73页第三章 有限状态自动机3.3 非确定的有限自动机(NFA)例：设计一台NFA，使它能够接受0，1形成的字符串且该字符串的最后两位是01。设计分析 可以考虑以下情况：（1）在初始状态下，无论输入 1 还是输入 0 都是一种不可接受的状态；（2）在初始状态下，输入 0 时，是一种可能接受的状态；（3）在可能接受的状态下，输入 1 时，是可接受的状态。第37页/共73页第三章第三章 有限状态自动机有限状态自动机3.3 非确定的有限自动机(NFA)（2）DFA 和 NFA 的等价性定理：设L(MN)是由NFA MN 所接受的语言。则存在一个DFA MD，使得 L(MD)=L

16、(MN)。第38页/共73页第三章第三章 有限状态自动机有限状态自动机（1）形式定义3.4 有转换的有限状态自动机(-NFA)定义：有转换的NFA M 是一个五元组：=(Q,q0,F)其中，Q、q0、F的定义与NFA中的定义相同；：状态转换函数,：Q()p(Q)即对(q,a)Q()(q,a)=p1,p2,pmQ第39页/共73页第三章第三章 有限状态自动机有限状态自动机3.4 有转换的有限状态自动机(-NFA)（2）相关概念v 闭包 假设有转换的NFA=(Q,q0,F)，对qQ,q 的 闭包是指由状态 q 出发，经过有 限段 弧到达的状态以及q本身组成的状态集合。记为-CLOSURE(q)。若

17、PQ,那么-CLOSURE(P)=第40页/共73页第三章第三章 有限状态自动机有限状态自动机3.4 有转换的有限状态自动机(-NFA)（2）相关概念v 的定义 对qQ,w*,a 其中：第41页/共73页第三章第三章 有限状态自动机有限状态自动机3.4 有转换的有限状态自动机(-NFA)（2）相关概念v 的定义 对RQv 有 转换 NFA M 所接受的语言第42页/共73页第三章第三章 有限状态自动机有限状态自动机3.4 有转换的有限状态自动机(-NFA)（3）-NFA 与 NFA 的等价性定理：如果-NFA M 所接受的语言为L(M),那么存在一个NFA M1，使得 L(M1)=L(M)第4

18、3页/共73页第三章第三章 有限状态自动机有限状态自动机3.5 FA是正规语言的识别器由文法推导句子 Sa1A1 Sa1A1 A1a2A2 a1a2A2 .An-2an-1An-1 a1a2an-1An-2 An-1an a1a2an-1an自动机识别句子 (q0,a1)=q1 q0a1ana1q1a2an (q1,a2)=q2 a1a2q2a3an .(qn-1,an)=qn a1a2a3anqn qnF第44页/共73页第三章第三章 有限状态自动机有限状态自动机3.5 FA是正规语言的识别器定理：FA接受的语言是正规语言思路：假设一台DFA M,它所接受的语言是L(M),该语言能够被正规文

19、法推出。定理：正规语言能够被 FA 所接受思路：假设L是由正规文法产生的语言,构造一台自动机FA能够接受它。第45页/共73页第三章第三章 有限状态自动机有限状态自动机3.5 FA是正规语言的识别器例1：假设 RG G=(S,B,0,1,P,S)其中 P=S0B,B0B|1S|0 构造一台 NFA M,使得 L(M)=L(G)。例2：由例1的NFA M 构造一台DFA M1,使得 L(M1)=L(M)。例3：由例2的DFA M1 构造一个 RG G,使得 L(G)=L(M1)。第46页/共73页第三章第三章 有限状态自动机有限状态自动机3.6 FA的一些变形(1)双向有限自动机v 确定的双向有

20、限自动机（2DFA）2DFA是一个五元组=(Q,q0,F)其中，Q,q0,F的定义与DFA的定义一致 ：Q QL,R,S第47页/共73页第三章第三章 有限状态自动机有限状态自动机3.6 FA的一些变形(1)双向有限自动机v 格局变化v 2DFA所接受的语言L(M)=w|w*,q0w wp,pF第48页/共73页第三章第三章 有限状态自动机有限状态自动机3.6 FA的一些变形(2)带输出的有限自动机v Moor 机 一个Moor 机为六元组M=(Q,q0)其中，Q,q0的含义与DFA的一致。：为有限输出字母表 :为输出函数 Q 第49页/共73页第三章第三章 有限状态自动机有限状态自动机3.6

21、 FA的一些变形v Moor 机例：用Moor机设计一台模4往返计数器。第50页/共73页第三章第三章 有限状态自动机有限状态自动机3.6 FA的一些变形(2)带输出的有限自动机v Mealy 机 一个Mealy 机为六元组M=(Q,q0)其中，Q,q0的含义与Moor机的一致。:为输出函数 Q 第51页/共73页第三章第三章 有限状态自动机有限状态自动机3.6 FA的一些变形v Mealy 机例如：用Mealy机设计一台奇偶校验器。第52页/共73页第三章第三章 有限状态自动机有限状态自动机3.6 FA的一些变形v Moor机和Mealy 机的等价性第53页/共73页第三章第三章 有限状态自

22、动机有限状态自动机3.6 FA的一些变形(2)带输出的有限自动机v Moor机和Mealy 机的等价性定义：设M=(Q,q0)为一个Moor机，M=(Q,q0)为一个Mealy机，且b=(q0),若对于w*,都有 TM(w)=bTM(w)则称Moor机与Mealy机等价，记为MM。第54页/共73页第三章第三章 有限状态自动机有限状态自动机3.6 FA的一些变形(2)带输出的有限自动机定理：对每个Moor机 M1=(Q,q0)都存在一个Mealy机M2,使得M2 M1.定理：对每个Mealy 机 M1=(Q,q0)都存在一个Moor机M2,使得M2 M1.第55页/共73页第三章第三章 有限状

23、态自动机有限状态自动机例1：构造与Moor机描述的模4往返计数器等价的Mealy机。第56页/共73页第三章第三章 有限状态自动机有限状态自动机例2：给定一台Mealy机（如图所示），构造一台与它等价的Moor机。第57页/共73页第三章第三章 有限状态自动机有限状态自动机总结：v 概念：文法分类（0、1、2、3型文法）自动机分类（DFA NFA -NFA 2DFA Moor Mealy）v 自动机之间、与文法之间的等价转换Moor机Mealy机-NFANFADFARG2DFA第58页/共73页第四章第四章 正规表达式正规表达式4.1 正规表达式的形式定义v 定义：设是一个字母表，字母表上正规

24、式（Regular Expression,RE）和正规集定义如下：（1）是上的正规式，对应的正规集为；（2）是上的正规式，对应的正规集为；（3）对a，a是上的正规式，对应的正规 集为a；第59页/共73页第四章第四章 正规表达式正规表达式4.1 正规表达式的形式定义（4）如果r和s分别是上的正规式，对应的正 规集为R和S。那么 (r+s)为正规式，对应的正规集为RS；(rs)为正规式，对应的正规集为RS；(r*)为正规式，对应的正规集为R*（5）只有满足上述形式定义的表达式才是上的正规式，它所表达的语言是正规集。第60页/共73页第四章第四章 正规表达式正规表达式4.1 正规表达式的形式定义例

25、如：假设=a,b(1)(a+b)*)(2)(ab*)(3)(b(a+b)*)(4)(a+b)*(aa)+(bb)(a+b)*)(5)（(a*)b)a*)b)a*）第61页/共73页第四章第四章 正规表达式正规表达式v正规表达式的运算性质 假设r,s,t都是上正规式，则有以下性质：（1）结合律；（2）分配律；（3）交换律；（4）幂等律；（5）加运算单位元；（6）乘运算单位元；（7）乘运算零元；（8）(r*)*=r*；（9）r*=r+；（10）*=（11）*=4.1 正规表达式的形式定义第62页/共73页第四章第四章 正规表达式正规表达式4.2 正规表达式与FA的等价 假设 r 是上的正规式，M

26、是一个 FA。若L(r)=L(M)，则称正规式 r 与 FA M 等价。第63页/共73页第四章第四章 正规表达式正规表达式4.2 正规表达式与FA的等价定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(1)运算符个数为0q0qfq0aq0qf第64页/共73页第四章第四章 正规表达式正规表达式定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(2)运算符个数不为0 r=r1+r2M2M1q0f1q1f2q2f0第65页/共73页第四章第四章 正规表达式正规表达式定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(2)运

27、算符个数不为0 r=r1r2M2M1f1q1f2q2第66页/共73页第四章第四章 正规表达式正规表达式定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(2)运算符个数不为0 r=r1*M1q0f1q1f0第67页/共73页第四章第四章 正规表达式正规表达式4.2 正规表达式与FA的等价定理：设 L 是被 DFA M 接受的语言，则 L 可以被正规表达式表示。第68页/共73页第四章第四章 正规表达式正规表达式4.2 正规表达式与FA的等价其中，1 i,j,k n第69页/共73页-NFANFADFARGRE第四章 正规表达式4.2 正规表达式与FA的等价第70页/共73页第五章第五章 正规语言的性质正规语言的性质5.1 Pumping 引理定理：假设 为有限字母表，L*。若 L 是正规语言，那么存在正整数 n 使得对任意的w1,w2,w3*,当w1w2w3L 并且|w2|n,可以写成 w2=,这里，|n.则 w1kw3L (k=0,1,2,.)。(1)Pumping 引理的提出第71页/共73页第五章第五章 正规语言的性质正规语言的性质5.1 Pumping 引理(1)Pumping 引理的提出第72页/共73页感谢您的观看！第73页/共73页