chapter有穷状态自动机实用PPT学习教案

1、会计学1chapter有穷状态自动机实用有穷状态自动机实用第三章、有穷状态自动机第三章、有穷状态自动机q1q22q3q434余额余额q6q5这就是我们天天见到的售货机，也称为自动机。第1页/共33页第三章、有穷状态自动机第三章、有穷状态自动机一、有穷状态自动机的形式定义一、有穷状态自动机的形式定义 定义1、 确定的有穷状态自动机是一个五元组（Q, , , q0, F ）,其中 (1)、 Q是有限状态集； (2) 、是字母表； (3)、 ：Q Q称为状态转换函数，它是状态集与字 母表的笛卡尔积到状态集的一个映射； (4) 、q0Q是初始状态； (5) 、 F是终止状态集。第2页/共33页第三章、

2、有穷状态自动机第三章、有穷状态自动机 有穷状态自动机是具有离散输入和输出的系统的一种数学有穷状态自动机是具有离散输入和输出的系统的一种数学模型。模型。 其主要特点有以下几个方面：其主要特点有以下几个方面： (1)、 系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。 (2)、 我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。 (3) 、系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。 (4)、 系统中有一个状态，它是系统的开始状态。 (5) 、系

3、统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子。第3页/共33页第三章、有穷状态自动机第三章、有穷状态自动机例如例如机器运行时：机器运行时：010: reject 11: accept 010100100100100: accept 010000010010: reject : rejectq1q210,1q1q3100第4页/共33页第三章、有穷状态自动机第三章、有穷状态自动机二、设计有穷自动机二、设计有穷自动机 就是针对给定的语言，你来设计一台自动机，并且准确识别这 个语言。确定性的有穷自动机记为DFA。 定义：如果一个语言被一台有穷自动机识别，则称它是正则语言。

4、例1、假设字母表为0,1，所考虑的语言由所以含有奇数个1的字 符串组成，构造一个识别这个语言的所有字符串的DFA的状 态图。 大家先设计。第5页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q1q20011第6页/共33页第三章、有穷状态自动机第三章、有穷状态自动机例2、假设字母表为0,1，构造一个识别含有001子串的所有 字符串的DFA的状态图。第7页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q1q2q3001q410,110例2、假设字母表为0,1，构造一个识别含有001字串的所有 字符串的DFA的状态图。第8页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q1

5、q2q3001q410,110例2、假设字母表为0,1，构造一个识别含有001子串的所有 字符串的DFA的状态图。第9页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q2q300,11q010q110例3、假设字母表为0,1，构造一个识别从1开始以0结束的 所有字符串的DFA的状态图。第10页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q1例4、假设字母表为0,1，构造一个识别空集的DFA的状态图。q1例5、假设字母表为0,1，构造一个识别L(E)=的DFA的状态图。第11页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q2q1q300,11例6、假设字母表为0,1，

6、构造一个识别L(E)=0,的DFA的状态图。0,1第12页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q1q20011比如例1的自动机的形式描述：（1）、Q=q1,q2;（2）、 =0,1；（3）、 (q1,0)=q1, (q1,1)=q2, (q2,0)=q2, (q2,1)=q1；（4）、q1为起始状态；（5）、F=q2为接受状态集。第13页/共33页第三章、有穷状态自动机第三章、有穷状态自动机问题（讨论）：问题（讨论）：1、DFA如何进行运算？第14页/共33页第三章、有穷状态自动机第三章、有穷状态自动机三、正则运算三、正则运算 在算术中，基本对象是数，工具是处理数的运算，如+

7、，；在计算理论中，对象是语言，工具是处理语言所设计的如下3种运算，称作正则运算。 定义：设A和B为语言，则下列3种运算称作正则运算。 （1）并：AB=x xA或x B （2）连接：AB=xy xA且x B （3）星号：A*=x1 x2xk xiA，i=1, k,k0 例1、=0,1，A=01,11，B=001,100，则 AB=01,11,001,100； AB=01001,01100,11001,11100； A*=，01,11,0101,0111,1101,1111,010101，。注意： = ， = ， *=， A = 第15页/共33页第三章、有穷状态自动机第三章、有穷状态自动机定义：

8、如果一个语言被一台有穷自动机识别，则称它是正则语言。 定义：如果DFA M1和DFA M2识别的语言分别为L(M1)和L(M2)，且L(M1)= L(M2)，称M1与M2等价。 下面如何演绎规则？ 首先，封闭性 ： A=1,2,3关于数字的加法不封闭； N=1,2,3,关于数字的加法封闭。那么，正则语言关于并运算，如何？第16页/共33页第三章、有穷状态自动机第三章、有穷状态自动机定理：正则语言类在并运算下封闭。证明：思路：即假设A，B正则，再证明AB正则。 设自动机M1，M2分别识别A，B ，造一个M识别AB即可。M1=（Q1,1,q1,F1), M2=（Q2,2,q2,F2),下面开始构造

9、一个M=（Q,q0,F)使其符合要求。（1）Q=（r1，r2) r1A1且r2A2=Q1Q2;（2） 相同，若不同，则= 1 2;（3）转移函数：任意（r1，r2) Q，a ，令 （r1，r2) ，a）= （1 （r1，a) ， 2（r2，a）， 于是， 取M的一个状态和一个输入符号，返回M的下一个状 态;（4）q0是有序对（q1,q2);（5）F=(r1,r2) r1F1或r2F2 （注意，FF1F2） 综上，我们构造了自动机M。第17页/共33页第三章、有穷状态自动机第三章、有穷状态自动机 该定理不仅证明了这个结论，更重要的是为我们的运算提供了方法。 例2、通过运算构造DFA： L(M)=

10、w w含偶数个0或二个1。解：令L(M1)=w w含偶数个0， L(M2)=w w含二个1。 则L(M)= L(M1) L(M2)，其中，q200q010q1111M1第18页/共33页第三章、有穷状态自动机第三章、有穷状态自动机q41q021q3000q50,11M2M1=（Q1,1,q1,F1), M2=（Q2,2,q2,F2),（1）、Q1=q01,q1,q2 , Q2=q02,q3,q4,q5;（2）、 = 0,1;（3）、转移函数1, 2如下表；（4）、q01，q02分别是M1,M2的起始状态； （5）、F1=q2， F2=q4.第19页/共33页第三章、有穷状态自动机第三章、有穷状

11、态自动机101q01q1q01q1q2q1q2q1Q2201q02q02q3q3q3q4q4q4q5q5q5q5第20页/共33页第三章、有穷状态自动机第三章、有穷状态自动机下面构造M= （Q,q,F)，（1）Q=(r1,r2) r1Q1且r2Q2；（2）= 0,1；（3）转移函数 （r1,r2) ,a）= （1 （r1,a) , 2（r2，a）， 如下页表所示；（4）q0=（q01，q02）是M的起始状态； （5）F=（q2,q02)，(q2,q3)，(q2,q4），(q2,q5)，(q01,q4)， (q1,q4)。第21页/共33页第三章、有穷状态自动机第三章、有穷状态自动机01（q01

12、,q02）（q1,q02）（q01,q3）（q01,q3）（q1,q3）（q01,q4）（q01,q4）（q1,q4）（q01,q5）（q01,q02）（q1,q5）（q01,q5）（q1,q02）（q2,q02）（q1,q3）（q1,q3）（q2,q3）（q1,q4）（q1,q4）（q2,q4）（q1,q5）（q1,q5）（q2,q5）（q1,q5）（q2,q02）（q1,q02）（q2,q3）（q2,q3）（q1,q3）（q2,q4）（q2,q4）（q1,q4）（q2,q5）（q2,q5）（q1,q5）（q2,q5）第22页/共33页第三章、有穷状态自动机第三章、有穷状态自动机(q01，q

13、02)01(q1，q02)(q2，q02)001101(q2，q4)0011(q01，q3)01(q1，q3)(q2，q3)0011(q01，q5)1(q1，q5)(q2，q5)01100(q01，q4)(q1，q4)那么，还可以证明，连接运算与星运算也是封闭的。第23页/共33页第三章、有穷状态自动机第三章、有穷状态自动机四、非确定性四、非确定性 前面所有的有穷自动机都是确定性的，记为DFA，特点是必须每个符 号都有相应的运算结果，自然的，考虑非确定性NFA，为推广，它在 任何一点，下一个状态可能存在若干个选择。那么，区别在哪里呢？q200q010q1111q20q010,q10,10,1第

14、24页/共33页第三章、有穷状态自动机第三章、有穷状态自动机那么，NFA如何计算呢？对于一个输入串，它能以多种行进方式到达一个状态，比如，输入01，下面是它的运算：从而，该机器识别01字符串。q2q01q011q1q01q1q20001第25页/共33页第三章、有穷状态自动机第三章、有穷状态自动机NFA的形式定义： 定义2、 非确定的有限自动机是一个五元组（Q,q0,F ）,其中 (1) Q是有限状态集； (2) 是字母表； (3) ：Q P（Q）称为状态转换函数，它是状态集 与字母表的笛卡尔积到状态集的一个映射， = ，P（Q）为Q的幂集； (4) q0Q是初始状态； (5) F是终止状态集

15、。第26页/共33页第三章、有穷状态自动机第三章、有穷状态自动机 考虑非确定性NFA，为DFA的推广，它在任何一点，下一个状态可能存在若干个选择。那么，区别在哪里呢？主要是转移函数,有很多计算分支，如果这些子过程中至少有一个接受，那么整个计算接受。为了适应，大家运算一下010001110，100110，11111111。非确定性NFA比DFA构造容易，实际上也是对能力更强的计算模型的非确定性的一个很好的引入。 关键关键问题：问题：DFA与NFA等价吗？第27页/共33页第三章、有穷状态自动机第三章、有穷状态自动机第28页/共33页第三章、有穷状态自动机第三章、有穷状态自动机NFA与与DFA的的等价性等价性 NFA与DFA等价是指两种模型识别相同的语言类（正则语言）。对于任意给定的DFA，存在一个NFA与之等价；对于任意给定的NFA，存在一个DFA与之等价。 DFA本身就是一种NFA，所以，要证明DFA与NFA等价，只需证明对于任意给定的NFA，存在一个DFA与之等价。 下面根据给定的NFA构造一个DFA：这里M2=（Q2,q0,F ），Q2 =P(Q），