《第三章有限状态自动机图文.ppt》由会员分享，可在线阅读，更多相关《第三章有限状态自动机图文.ppt（74页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 有限状态自动机有限状态自动机 主要内容主要内容确定的有限状态自动机确定的有限状态自动机(DFA)不确定的有限状态自动机不确定的有限状态自动机(NFA)带空移动的有限状态自动机带空移动的有限状态自动机(-NFA)带输出的有限状态自动机带输出的有限状态自动机2021/3/101有限状态系统实例有限状态系统实例指针式钟表共有指针式钟表共有12*60*60个状态，每过个状态，每过一秒，钟表就从一种状态到另一种状态。一秒，钟表就从一种状态到另一种状态。围棋共有围棋共有3361个状态，每走一步棋就从一个状态，每走一步棋就从一个状态到另一个状态。个状态到另一个状态。电视开电视开电视关电视关打开关
2、闭2021/3/102有限状态系统有限状态系统淘宝网上购物淘宝网上购物顾客、店家和支付宝网三方之间的交互限于以下几种事件：顾客、店家和支付宝网三方之间的交互限于以下几种事件：1、顾客告诉店家购买某种物品，决定、顾客告诉店家购买某种物品，决定预付款预付款购物。购物。 并将钱款转入支并将钱款转入支付宝。付宝。2、顾客决定、顾客决定取消取消预付款。预付款。 顾客通知顾客通知支付宝支付宝，把购物这笔钱保留在自，把购物这笔钱保留在自己的银行帐号上。己的银行帐号上。3、店家、店家送货送货给顾客。给顾客。4、顾客收到货后、顾客收到货后 （1）确认付款确认付款。 通通知支付宝将钱款划拨到店家帐号，知支付宝将钱
3、款划拨到店家帐号， 转到转到（5） （2）退货退货。把购物这笔钱保留在自己的银行帐号上，结束。把购物这笔钱保留在自己的银行帐号上，结束。 （3）换货换货。寄回店家，店家重。寄回店家，店家重送货送货给顾客。给顾客。5、支付宝将这笔钱、支付宝将这笔钱转帐转帐。 把顾客购物这笔钱划拨给店家的帐号。把顾客购物这笔钱划拨给店家的帐号。以上的事件以及事件间在一定条件下转化的情况，可以表以上的事件以及事件间在一定条件下转化的情况，可以表示成有限状态系统，每个状态表示某一方所处的局面。示成有限状态系统，每个状态表示某一方所处的局面。2021/3/103选物品选物品预付款已购物已购物送货已收货已收货换货更换物品
4、更换物品选物品选物品预付款已购物已购物确认付款认可物品认可物品退货不认可物品不认可物品换货取消选物品选物品已购物已购物确认付款认可物品认可物品转帐交易结束交易结束不认可物品不认可物品取消取消2021/3/1043.1 语言的识别语言的识别 推导和归约中的回溯问题将对系统的效率产推导和归约中的回溯问题将对系统的效率产生极大的影响生极大的影响 SaA|aB AaA|c BaB|d 系统识别语言系统识别语言anc|n1and|n1的字符的字符串过程中状态的变化图示如上串过程中状态的变化图示如上 2021/3/105识别系统识别系统(模型模型) 系统有有限个状态，不同状态代表不同的规系统有有限个状态，
5、不同状态代表不同的规定任务。定任务。 输入字符串中出现的字符构成一个字母表。输入字符串中出现的字符构成一个字母表。系统处理的所有字符串都是这个字母表上的字系统处理的所有字符串都是这个字母表上的字符串。符串。 系统在任何一个状态下，从输入字符串中系统在任何一个状态下，从输入字符串中读入字符后，可转到新的状态（或状态不读入字符后，可转到新的状态（或状态不变）。下一次再读时，会读入下一个字符。变）。下一次再读时，会读入下一个字符。2021/3/106 系统中有一个开始状态，系统在这个状态系统中有一个开始状态，系统在这个状态下开始进行某个给定句子的处理。下开始进行某个给定句子的处理。 系统中有一些状态
6、表示它到目前为止所读系统中有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。就是系统所能识别的语言。 2021/3/107相应的物理模型相应的物理模型一个右端无穷的输入带。一个右端无穷的输入带。一个有限状态控制器一个有限状态控制器(finite state control,FSC) 。一个读头。一个读头。 系统的每一个动作由三个节拍构成：系统的每一个动作由三个节拍构成： 读
7、入读头正注视的字符；读入读头正注视的字符； 根据当前状态和读入的字符改变有限控制器的状态；根据当前状态和读入的字符改变有限控制器的状态； 将读头向右移动一格。将读头向右移动一格。 2021/3/1083.2有限状态自动机有限状态自动机 有限状态自动机有限状态自动机(finite automaton,FA)是一个五元组：M=(Q， q0，F)Q状态的非空有限集合。状态的非空有限集合。 qQ，q为为M的一个的一个状态状态。输入字母表输入字母表。输入字符串都是。输入字符串都是上的字符串。上的字符串。 q0q0Q，是是M的的开开始始状状态态（初初始始状状态态或或者者启启动动状态）。状态）。2021/3
8、/109状态状态转移函数转移函数(转换函数转换函数或或移动函数移动函数)， ：QQ，对，对 (q，a)Q，(q，a)=p表示：表示：M在状态在状态q读入字符读入字符a，将状态变，将状态变成成p，并将读头指向输入字符串的下一个字，并将读头指向输入字符串的下一个字符。符。FF Q，是，是M的的终止状态终止状态集合集合。 qF，q称称M的的终止状态终止状态（接受状态）。（接受状态）。 状态转移图状态转移图状态转换图状态转换图2021/3/1010例例 有限状态自动机有限状态自动机 M1=(q0，q1，q2，0，1，q0，q2)其中其中 ：1(q0,0)= q1 1(q1,0)= q2， 1(q2,0
9、)= q1q00q1S0q20识别识别 (00)n|n=12021/3/1011有限自动机的表示有限自动机的表示（1 1）转移图表示法）转移图表示法2021/3/1012（2 2）矩阵表示法）矩阵表示法 符号状态0q0（初始）q1q1q2q2（终止）q12021/3/1013确定的有限状态自动机确定的有限状态自动机对于任意的对于任意的qQ， a，(q，a)均有确定均有确定的值，这种的值，这种FA称为称为确定的有限状态自动机确定的有限状态自动机(deterministic finite automaton，DFA) M接受接受(识别识别)的语言的语言 对于对于 x*如果如果(q0，x)F，则称，
10、则称x被被M接受。接受。L(M)=x| x*且且(q0，x)F称为由称为由M接受接受(识别识别)的语言的语言 2021/3/1014：QQ，对，对 (q，a)Q，：Q*Q，对，对 (q，w)Q，对任意的对任意的qQ，w*，a，定义，定义 (1)(q, )= q(2)(q,wa)= ( (q,w),a)(q,a)= (q, a) = ( (q, ),a) = (q,a)2021/3/1015对于对于(q0,0)= q1, (q1,1)= q2, (q2,0)= q3,(q0,010)=( (q0,01),0)=( (q0,0),1),0)=( (q0,),0) ,1),0)=(q0,0) ,1)
11、,0)=(q1 ,1),0)=(q2 ,0)= q3不用区分这两个符号不用区分这两个符号2021/3/10162021/3/1017例例 构造一个构造一个DFA，它接受的语言为，它接受的语言为x000y|x，y0，1*q0M的启动状态；的启动状态；q1M读读到到了了一一个个0，这这个个0可可能能是是子子串串“000”的的第第1个个0；q2M在在q1后后紧紧接接着着又又读读到到了了一一个个0，这这个个0可可能能是子串是子串“000”的第的第2个个0；q3M在在q2后后紧紧接接着着又又读读到到了了一一个个0，发发现现输输入入字字符符串串含含有有子子串串“000”；因因此此，这这个个状状态态应应该该
12、是是终终止状态。止状态。2021/3/1018(q0,1)= q0M在在q0读读到到了了一一个个1，它它需需要要继继续续在在q0 “等等待待”可可能能是是子子串串“000”的的第第1个个0的输入字符的输入字符0；(q1,1)= q0M在在刚刚刚刚读读到到了了一一个个0后后，读读到到了了一一个个1，表表明明在在读读入入这这个个1之之前前所所读读入入的的0并并不不是是子子串串“000”的的第第1个个0，因因此此，M需需要要重重新新回回到到状状态态q0，以以寻寻找找子子串串“000”的第的第1个个0；2021/3/1019(q2,1)= q0M在在刚刚刚刚发发现现了了00后后，读读到到了了一一个个1
13、，表表明明在在读读入入这这个个1之之前前所所读读入入的的00并并不不是是子子串串“000”的的前前两两个个0，因因此此，M需需要要重重新新回回到到状状态态q0，以以寻寻找找子子串串“000”的的第第1个个0；(q3,0)= q3M找找到到了了子子串串“000”，只只用用读入该串的剩余部分。读入该串的剩余部分。(q3,1)= q3M找找到到了了子子串串“000”，只只用用读入该串的剩余部分。读入该串的剩余部分。2021/3/1020M=(q0，q1，q2，q3，0，1， (q0,0)= q1，(q1,0)= q2，(q2,0)= q3，(q0,1)= q0，(q1,1)= q0，(q2,1)=
14、q0，(q3,0)= q3，(q3,1)= q3，q0，q3) 2021/3/1021例例 构造一个构造一个DFA，它接受的语言为，它接受的语言为x000|x0，1*。状态状态q0读到的读到的0可能是输入字符串的最后三个可能是输入字符串的最后三个0的第的第1个个0；在在状状态态q1紧紧接接着着读读到到的的0可可能能是是输输入入字字符符串串的的最最后三个后三个0的第的第2个个0；在在状状态态q2紧紧接接着着读读到到的的0可可能能是是输输入入字字符符串串的的最最后三个后三个0的第的第3个个0；2021/3/1022在在状状态态q3紧紧接接着着读读到到的的0也也可可能能是是输输入入字字符符串串的的最
15、后三个最后三个0的第的第3个个0；如果在状态如果在状态q1，q2，q3读到的是读到的是1，则要重新检，则要重新检查输入串是否以三个查输入串是否以三个0结尾。结尾。 2021/3/1023接受语言接受语言x000|x0，1*x001|x0，1*的的FA 2021/3/1024例例 构造一个构造一个DFA，它接受的语言为，它接受的语言为0n1m2k|n,m,k1。 q0M的启动状态；的启动状态；q1M读读到到至至少少一一个个0，并并等等待待读读更更多多的的0；q2M读读到到至至少少一一个个0后后，读读到到了了至至少少一一个个1，并等待读更多的，并等待读更多的1；q3M读到至少一个读到至少一个0后跟
16、至少一个后跟至少一个1后，后，并且接着读到了至少一个并且接着读到了至少一个2。 2021/3/1025先设计先设计“主体框主体框架架”再补充细节再补充细节 当当FA进入进入qt就无法离开此状态。就无法离开此状态。qt相当于一个相当于一个陷阱陷阱状态状态(trap)。一般将陷阱状态用作发现输入串不可。一般将陷阱状态用作发现输入串不可能是该能是该FA所识别的语言的句子时进入的状态。在所识别的语言的句子时进入的状态。在此状态下，此状态下，FA读完输入串中剩余的字符。读完输入串中剩余的字符。 2021/3/1026例例 构造一个构造一个DFA，它接受的语言为，它接受的语言为x|x0，1*，且当把且当把
17、x看成二进制数时，看成二进制数时，x模模3与与0同余同余。 分析：换句话说，分析：换句话说，x要能被要能被3整除。整除。当二进制数当二进制数x的位数向右不断增加时，它的值（换算成十进制）的位数向右不断增加时，它的值（换算成十进制）的增加很有规律：的增加很有规律：x0的值等于的值等于2x，x1的值等于的值等于2x+1。例如例如x=100，它的十进制值是，它的十进制值是4，右边添上，右边添上0后为后为1000，它的，它的十进制值是十进制值是8；右边添上；右边添上1后为后为1001，它的十进制值是，它的十进制值是9。如如x模模3余余1，则，则2x模模3余余2，而，而2x+1模模3余余3，即能被，即能
18、被3整除了。整除了。又如有某个又如有某个x模模3余余2，则，则2x模模3余余4，而余数，而余数4大于大于3，被，被3除余除余1，所以，所以2x模模3余余1；而；而2x+1模模3余余5，相当于模，相当于模3余余2。经这样分析以后，经这样分析以后，FAM除初始状态外，只需要设除初始状态外，只需要设3个状态：模个状态：模3余余0状态（即终结状态），模状态（即终结状态），模3余余1状态，模状态，模3余余2状态。状态。2021/3/1027接受语言接受语言x|x0，1*，且当把，且当把x看成二进看成二进制数时，制数时，x模模3与与0同余同余的的DFA如下：如下： 2021/3/1028qs0S10q00
19、能被能被3整除整除q1101模模3余余100能被能被3整除整除01模模3余余1q210模模3余余20111能被能被3整除整除100模模3余余11101模模3余余2接受的语言是由一切含有偶数个接受的语言是由一切含有偶数个0和偶数个和偶数个1的字符串组成的集合。的字符串组成的集合。2021/3/1029确定有限自动机的程序设计确定有限自动机的程序设计 q=m_qqd2021/3/10302024/9/21313.3 不确定有限自动机不确定有限自动机一个非确定的有限自动机一个非确定的有限自动机(Nondeterministic Finite Automata)简记为简记为NFA，是一个五元组，是一个
20、五元组M=(Q,q0 , F)其中其中Q、q0和和F与确定的有限自动机的含意相同，只是转与确定的有限自动机的含意相同，只是转移函数移函数的定义不同，它是从的定义不同，它是从Q到到2Q（Q的一切子集的集的一切子集的集合）上的映射。合）上的映射。在在DFA中，中，的一般形式是的一般形式是(q,a)=p (q,pQ)，而在，而在NFA中，中，的一般形式是的一般形式是(q,a)=p1,p2,pk(piQ,i=1,2,k)，或，或(q,a)=（空集）。（空集）。在在NFA中转移函数中转移函数的取值是一个状态集，即使只有一个状的取值是一个状态集，即使只有一个状态态p，也要写成集合形式，也要写成集合形式p。
21、2021/3/1031希望是接受希望是接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA如下：如下：2021/3/1032希望是接受希望是接受x|x0，1*，且，且x 的倒数第的倒数第10个字符为个字符为1的的FA如下如下 ：2021/3/1033这这两两个个图图所所给给的的“FA”与与前前面面我我们们所所定定义义的的FA，即，即DFA，的区别在于：，的区别在于： 并并不不是是对对于于所所有有的的(q，a)Q,(q，a)都有一个状态与它对应；都有一个状态与它对应； 并不是对于所有的并不是对于所有的(q，a)Q,(q，a)只对应一个状态。只对应一个状态。 “FA”在任意时刻可以处于
22、有限多个状态。在任意时刻可以处于有限多个状态。 2021/3/1034对于一个输入字符，对于一个输入字符，NFA与与DFA的差异是前的差异是前者可以进入若干个状态，而后者只能进入者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从一个惟一的状态。虽然从DFA看待问题的看待问题的角度来说，角度来说，NFA在某一时刻同时进入若干在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的个状态，但是，这若干个状态合在一起的“总效果总效果”相当于它处于这些状态对应的相当于它处于这些状态对应的一个一个“综合状态综合状态”。因此，我们考虑让。因此，我们考虑让DFA用一个状态去对应用一个状态去对应NF
23、A的一组状态。的一组状态。 2021/3/1035NFA与与DFA等价等价 NFA M1=(Q，1，q0，F1)与与DFA M2=(Q2，2，q0，F2)的对应关系：的对应关系：NFA从开始状态从开始状态q0启动，我们就让相应的启动，我们就让相应的DFA从状态从状态q0启动。所以启动。所以q0= q0。 对于对于NFA 的一个状态组的一个状态组q1，q2，qn，如，如果果NFA在此状态组时读入字符在此状态组时读入字符a后可以进入状态后可以进入状态组组p1，p2，pm,则让相应的则让相应的DFA在状态在状态q1，q2，qn读入字符读入字符a时，进入状态时，进入状态p1，p2，pm。 2021/3
24、/1036构造给定构造给定NFA等价的等价的DFA策略策略先只把开始状态先只把开始状态q0填入表的状态列中，如果填入表的状态列中，如果表中所列的状态列有未处理的，则任选一个未表中所列的状态列有未处理的，则任选一个未处理的状态处理的状态q1，q2，qn，对，对中的每个字中的每个字符符a，计算，计算(q1，q2，qn，a)，并填入相，并填入相应的表项中，如果应的表项中，如果(q1，q2，qn，a)在在表的状态列未出现过，则将它填入表的状态列。表的状态列未出现过，则将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处如此重复下去，直到表的状态列中不存在未处理的状态。理的状态。 2021/3/
25、1037从从NFA构造等价的构造等价的DFA更为实用的方法是采取以更为实用的方法是采取以下步骤：下步骤： 从状态从状态q0出发，通过状态转移函数出发，通过状态转移函数，逐步扩充，逐步扩充状态集；每一步仅对状态集中新增加的状态，才状态集；每一步仅对状态集中新增加的状态，才写出状态转移函数；此过程一直继续下去，直到写出状态转移函数；此过程一直继续下去，直到不再增加新的状态为止，最后就得到了不再增加新的状态为止，最后就得到了DFA。2021/3/1038 第一步第一步 从从q0开始：开始：(q0,0)=q0,q1, (q0,1)=q0,q2。第二步第二步 处理两个新状态处理两个新状态q0,q1和和q
26、0,q2 ：( q0,q1,0)=q0,q1,q3， ( q0,q1,1)=q0,q2； ( q0,q2,0)=q0,q1， ( q0,q2,1)=q0,q2,q3。第三步第三步 处理新增加的两个状态处理新增加的两个状态q0,q1,q3和和q0,q2,q3 ：(q0,q1,q3,0)=q0,q1,q3, (q0,q1,q3,1)=q0,q2,q3；(q0,q2,q3,0)=q0,q1,q3, (q0,q2,q3,1)=q0,q2,q3。到这一步为止，不再增加新的状态，所求的到这一步为止，不再增加新的状态，所求的DFA只包含只包含5个状态。个状态。2021/3/1039NFA的等价的等价DFA
27、2021/3/10402021/3/1041第一步第一步 从从q0开始：开始：(q0,0)=q0,q3, (q0,1)=q0,q1。第二步第二步 处理两个新状态处理两个新状态q0,q3和和q0,q1 ：( q0,q3,0)=q0,q3,q4， ( q0,q3,1)=q0,q1； ( q0,q1,0)=q0,q3， ( q0,q1,1)=q0,q1,q2。第三步第三步 处理新增加的两个状态处理新增加的两个状态q0,q3,q4和和q0,q1,q2 ：(q0,q3,q4,0)=q0,q3,q4, (q0,q3,q4,1)=q0,q1,q4；(q0,q1,q2,0)=q0,q3,q2, (q0,q1,
28、q2,1)=q0,q1,q2。第四步第四步 处理新增加的两个状态处理新增加的两个状态q0,q1,q4和和q0,q3,q2：(q0,q1,q4,0)=q0,q3,q4, (q0,q1,q4,1)=q0,q1,q2,q4；(q0,q3,q2,0)=q0,q3,q4,q2, (q0,q3,q2,1)=q0,q1,q2。第五步第五步 处理新增加的两个状态处理新增加的两个状态q0,q1,q2,q4和和q0,q3,q4,q2 ：(q0,q1,q2,q4,0)=q0,q3,q4,q2, (q0,q1,q2,q4,1)=q0,q1,q2,q4； (q0,q3,q4,q2,0)=q0,q3,q4,q2, (q0
29、,q3,q4,q2,1)=q0,q1,q2,q4。 到这一步为止，不再增加新的状态，所求的到这一步为止，不再增加新的状态，所求的DFA只包含只包含9个状态。个状态。2021/3/1042Q00Q03S1Q0141Q0100011Q034Q012Q032Q0234Q012401100110012021/3/1043有限自动机的应用有限自动机的应用在文本中查找字符串在文本中查找字符串用于文本搜索用于文本搜索识别关键字集合识别关键字集合2021/3/1044在在WebWeb和其它在线文本库时代，一个常见的问题是，给和其它在线文本库时代，一个常见的问题是，给定一个单词集合，查找包含一个（或全部）单词的
30、所有定一个单词集合，查找包含一个（或全部）单词的所有文档。搜索引擎是完成这个任务的一个专门的软件，它文档。搜索引擎是完成这个任务的一个专门的软件，它对对WebWeb上出现的每个单词（大约有一亿种不同的英文单上出现的每个单词（大约有一亿种不同的英文单词），保存这个单词所有出现之处的列表。要用非常大词），保存这个单词所有出现之处的列表。要用非常大的主存的计算机保持这些列表的最常见部分，以便随时的主存的计算机保持这些列表的最常见部分，以便随时可用，允许许多人在瞬间搜索这些文档。可用，允许许多人在瞬间搜索这些文档。虽然在搜索引擎中常用的倒排索引技术没有使用有穷自虽然在搜索引擎中常用的倒排索引技术没有使
31、用有穷自动机，但有许多有关的应用不适合使用倒排索引动机，但有许多有关的应用不适合使用倒排索引, ,但很但很适合于应用基于自动机的技术。适合于应用基于自动机的技术。2021/3/1045适合应用自动机技术来搜索的特征是：适合应用自动机技术来搜索的特征是：所搜索的数据库快速变化。例如：所搜索的数据库快速变化。例如：（a a）每一天，新闻分析员希望搜索当天在线的新闻文）每一天，新闻分析员希望搜索当天在线的新闻文章来寻找有关话题。比如，金融分析员可能搜索他感兴章来寻找有关话题。比如，金融分析员可能搜索他感兴趣的股票代码或公司名称。趣的股票代码或公司名称。（b b）“采购机器人采购机器人”软件希望搜索顾
32、客要求的商品的软件希望搜索顾客要求的商品的当前价格。当前价格。“机器人机器人”从从WebWeb上获得当前的目录页面，上获得当前的目录页面，然后搜索这些页面寻找提示具体商品价格的单词。然后搜索这些页面寻找提示具体商品价格的单词。所搜索的文档不能建立目录。出于商业机密的考虑，有所搜索的文档不能建立目录。出于商业机密的考虑，有些公司（比如出版商）不愿意让人轻易发现本公司销售些公司（比如出版商）不愿意让人轻易发现本公司销售的所有书的所有页面。实际上，在响应查询的的所有书的所有页面。实际上，在响应查询的“一瞬间一瞬间”才生成这些页面。才生成这些页面。2021/3/1046NFA2021/3/1047DF
33、A2021/3/10483.4 带空移动的有限状态自动机带空移动的有限状态自动机 接受语言接受语言0n1m2k|n，m，k0的的NFA 2021/3/1049接受语言接受语言0n1m2k|n，m，k0的的NFA是否可是否可以构造成下图所示的以构造成下图所示的“-NFA ”？ 其构造显然比上图所示的其构造显然比上图所示的NFA更容易。更容易。当然还希望它们是等价的。当然还希望它们是等价的。它的它的函数是：函数是：(q0,0)=q0，(q1,1)=q1，(q2,2)=q2 (q0,)=q1，(q1,)=q2，2021/3/10502024/9/2151带空移动的不确定的有限状态自动机带空移动的不确
34、定的有限状态自动机(non-deterministic finite automaton with -moves,-NFA)M=(Q，q0，F)，Q、q0、F的意义同的意义同DFA。 ：Q()2Q 2021/3/1051非空移动非空移动 (q，a)Q(q，a)= p1，p2，pm表示表示M在状态在状态q读入字符读入字符a，可以选择地，可以选择地将状态变成将状态变成p1、p2、或者或者pm ，并将读，并将读头向右移动一个带方格而指向输入字符头向右移动一个带方格而指向输入字符串的下一个字符。串的下一个字符。2021/3/1052空移动空移动 qQ(q，)= p1，p2，pm表示表示M在状态在状态q
35、不读入任何字符，可以选不读入任何字符，可以选择地将状态变成择地将状态变成p1、p2、或者或者pm 。也。也可以叫做可以叫做M在状态在状态q做一个空移动做一个空移动(又可以又可以称为称为移动移动)，并且选择地将状态变成，并且选择地将状态变成p1、p2、或者或者pm。2021/3/1053例例定理定理 -NFA与与NFA等价。等价。2021/3/1054空闭包的定义空闭包的定义 在一个有在一个有转移的有限穷自动机中，用转移的有限穷自动机中，用-CLOSURE(q) CLOSURE(q) 表示状态表示状态q q的空闭包，它是下述定义的的空闭包，它是下述定义的状态集：状态集：(1)q(1)q在在-CL
36、OSURE(q)-CLOSURE(q)中；中；(2)(2)若若p p在在-CLOSURE(q)-CLOSURE(q)中，则中，则(p,)(p,)也都在也都在-CLOSURE(q)CLOSURE(q)中；中；(3)(3)重复重复(2)(2)，直到，直到-CLOSURE(q)-CLOSURE(q)中状态不再增加中状态不再增加为止。为止。从转移图上看，从转移图上看，-CLOSURE(q)-CLOSURE(q)就是从状态就是从状态q q出发，出发，沿着标有沿着标有的有向边所能达到的一切状态所构成的的有向边所能达到的一切状态所构成的集合（包括状态集合（包括状态q q本身）。本身）。2021/3/1055
37、对于状态集对于状态集P P的的-CLOSURE-CLOSURE，-CLOSURE(P) = -CLOSURE(q)-CLOSURE(P) = -CLOSURE(q)。-CLOSURE(q0)=q0,q1,q2-CLOSURE(q1)=q1,q2。2021/3/1056扩充转移函数扩充转移函数对于一个具有对于一个具有转移的有限穷自动机，它的扩充转移函转移的有限穷自动机，它的扩充转移函数数定义如下：定义如下： (q,)=-CLOSURE(q), (q,)=-CLOSURE(q), (q,wa)=-CLOSURE(P),P = (r,a) (q,wa)=-CLOSURE(P),P = (r,a)。其
38、中其中qQ, a, wqQ, a, w* *。注意，扩充转移函数注意，扩充转移函数已经不是已经不是的简单扩充，与的简单扩充，与完全不相同。完全不相同。2021/3/1057带空移动的自动机转为不确定自动机带空移动的自动机转为不确定自动机 00q00q1q2(q0,0)=-CLOSURE( (q0,),0) =-CLOSURE(q0,q1,q2,0)=-CLOSURE(q0) =q0,q1,q2 与与(q0,0)= q0不同不同2021/3/1058(q0,1)=-CLOSURE( (q0,),1)=-CLOSURE(q0,q1,q2,1)=-CLOSURE(q1)=q1,q2 0,10,1q0
39、0q1q22021/3/1059(q0,2)=-CLOSURE( (q0,),2) =-CLOSURE(q0,q1,q2,2) =-CLOSURE(q2) =q2 0,10,1,2q00q1q22021/3/1060(q1,0)=-CLOSURE( (q1,),0) =-CLOSURE(q1,q2,0)无定义无定义 (q1,1)=-CLOSURE( (q1,),1) =-CLOSURE(q1,q2,1) =-CLOSURE(q1) =q1,q2(q1,2)=-CLOSURE( (q1,),2) =-CLOSURE(q1,q2,2) =-CLOSURE(q2) =q22021/3/1061(q2
40、,0)=-CLOSURE( (q2,),0) =-CLOSURE(q2,0)无定义无定义(q2,1)=-CLOSURE( (q2,),1) =-CLOSURE(q2,1)无定义无定义(q2,2)=-CLOSURE( (q2,),2) =-CLOSURE(q2,2) =-CLOSURE(q2) =q22021/3/10623.5 带输出的带输出的FA Moore机机 M=(Q，q0) Q、q0、的意义同的意义同DFA。 输出字母表输出字母表(output alphabet)(output alphabet)。 ：Q为输出函数。对为输出函数。对 qQ，(q)=a表示表示M在状态在状态q时输出时输出
41、a。2021/3/1063输入的字符同时输出：输入的字符同时输出： ：(q0)=，(q1)=0，(q2)=1 (q3)=0， (q4)=1， ：(q0)=0|1，(q1)=0|1，(q2)=0|1 (q3)= ， (q4)= q0Sq1q300q2q411102021/3/1064例例 设计一个设计一个Moore机，机，=0，1，若将输入，若将输入串看成一个二进制数，要求在读入过程中，能串看成一个二进制数，要求在读入过程中，能输出它已读过子串的模输出它已读过子串的模3余数。余数。因为模因为模3余数只能有余数只能有0，1，2三个值，因此取三个值，因此取=0，1，2，并且只设三个状态，并且只设三个
42、状态q0,q1,q2，分别，分别对应这三种余数。对应这三种余数。qsS10q0q11q2011002021/3/10652021/3/10662021/3/1067Mealy机机 M=(Q，q0) 输出字母表。输出字母表。 ：Q为输出函数。对为输出函数。对 (q，a)Q，(q，a)=d表示表示M在状态在状态q读入读入字符字符a时输出时输出d。2021/3/1068输入的字符同时输出：输入的字符同时输出： ：(q0，0)=0， (q0，1)=1， (q1，0)=0， (q1，1)=1， (q2，0)=0， (q2，1)=1，q0Sq1q300q2q411102021/3/1069例例 给出一个给出一个0，1串的集合串的集合S，该集合中的串都，该集合中的串都以以00或或11结尾。要求设计一个只有两个输出符结尾。要求设计一个只有两个输出符号（号（=y,n）的）的Mealy机，当它读过属于集合机，当它读过属于集合S的串时，输出的串时，输出y，表示接受；当它读过不属于，表示接受；当它读过不属于集合集合S的串时，输出的串时，输出n，表示不接受。，表示不接受。2021/3/10702021/3/1071电子标签 http:/ 转为转为Mealy机机2021/3/1074
