有限状态自动机 (2).ppt

2023/10/15,1,第3章 有限状态自动机,主要内容确定的有限状态自动机(DFA)不确定的有限状态自动机(NFA),带空移动的有限状态自动机(-NFA)带输出的有限状态自动机,2023/10/15,2,有限状态系统实例,指针式钟表共有12*60*60个状态，每过一秒，钟表就从一种状态到另一种状态。围棋共有3361个状态，每走一步棋就从一个状态到另一个状态。,2023/10/15,3,有限状态系统淘宝网上购物,顾客、店家和支付宝网三方之间的交互限于以下几种事件：1、顾客告诉店家购买某种物品，决定预付款购物。并将钱款转入支付宝。2、顾客决定取消预付款。顾客通知支付宝，把购物这笔钱保留在自己的银行帐号上。3、店家送货给顾客。4、顾客收到货后（1）确认付款。通知支付宝将钱款划拨到店家帐号，转到（5）（2）退货。把购物这笔钱保留在自己的银行帐号上，结束。（3）换货。寄回店家，店家重送货给顾客。5、支付宝将这笔钱转帐。把顾客购物这笔钱划拨给店家的帐号。以上的事件以及事件间在一定条件下转化的情况，可以表示成有限状态系统，每个状态表示某一方所处的局面。,2023/10/15,5,3.1 语言的识别,推导和归约中的回溯问题将对系统的效率产生极大的影响 SaA|aB AaA|c BaB|d,系统识别语言anc|n1and|n1的字符串过程中状态的变化图示如上,2023/10/15,6,识别系统(模型)系统有有限个状态，不同状态代表不同的规定任务。输入字符串中出现的字符构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。,系统在任何一个状态下，从输入字符串中读入字符后，可转到新的状态（或状态不变）。下一次再读时，会读入下一个字符。,2023/10/15,7,系统中有一个开始状态，系统在这个状态下开始进行某个给定句子的处理。系统中有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。,2023/10/15,8,相应的物理模型一个右端无穷的输入带。一个有限状态控制器(finite state control,FSC)。一个读头。系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有限控制器的状态；将读头向右移动一格。,2023/10/15,9,3.2有限状态自动机,有限状态自动机(finite automaton,FA)是一个五元组：M=(Q，q0，F)Q状态的非空有限集合。qQ，q为M的一个状态。输入字母表。输入字符串都是上的字符串。q0q0Q，是M的开始状态（初始状态或者启动状态）。,2023/10/15,10,状态转移函数(转换函数或移动函数)，：QQ，对(q，a)Q，(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头指向输入字符串的下一个字符。FFQ，是M的终止状态集合。qF，q称M的终止状态（接受状态）。,状态转移图状态转换图,2023/10/15,11,例 有限状态自动机 M1=(q0，q1，q2，0，1，q0，q2)其中：1(q0,0)=q1 1(q1,0)=q2，1(q2,0)=q1,0,0,0,识别(00)n|n=1,有限自动机的表示,（1）转移图表示法,（2）矩阵表示法,2023/10/15,14,确定的有限状态自动机对于任意的qQ，a，(q，a)均有确定的值，这种FA称为确定的有限状态自动机(deterministic finite automaton，DFA),M接受(识别)的语言 对于x*如果(q0，x)F，则称x被M接受。L(M)=x|x*且(q0，x)F称为由M接受(识别)的语言,：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),对于(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),0)=(q1,1),0)=(q2,0)=q3,不用区分这两个符号,2023/10/15,18,例 构造一个DFA，它接受的语言为x000y|x，y0，1*q0M的启动状态；q1M读到了一个0，这个0可能是子串“000”的第1个0；q2M在q1后紧接着又读到了一个0，这个0可能是子串“000”的第2个0；q3M在q2后紧接着又读到了一个0，发现输入字符串含有子串“000”；因此，这个状态应该是终止状态。,2023/10/15,19,(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；,2023/10/15,20,(q2,1)=q0M在刚刚发现了00后，读到了一个1，表明在读入这个1之前所读入的00并不是子串“000”的前两个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0；(q3,0)=q3M找到了子串“000”，只用读入该串的剩余部分。(q3,1)=q3M找到了子串“000”，只用读入该串的剩余部分。,2023/10/15,21,M=(q0，q1，q2，q3，0，1，(q0,0)=q1，(q1,0)=q2，(q2,0)=q3，(q0,1)=q0，(q1,1)=q0，(q2,1)=q0，(q3,0)=q3，(q3,1)=q3，q0，q3),2023/10/15,22,例 构造一个DFA，它接受的语言为x000|x0，1*。状态q0读到的0可能是输入字符串的最后三个0的第1个0；在状态q1紧接着读到的0可能是输入字符串的最后三个0的第2个0；在状态q2紧接着读到的0可能是输入字符串的最后三个0的第3个0；,2023/10/15,23,在状态q3紧接着读到的0也可能是输入字符串的最后三个0的第3个0；如果在状态q1，q2，q3读到的是1，则要重新检查输入串是否以三个0结尾。,2023/10/15,24,接受语言x000|x0，1*x001|x0，1*的FA,2023/10/15,25,例 构造一个DFA，它接受的语言为0n1m2k|n,m,k1。q0M的启动状态；q1M读到至少一个0，并等待读更多的0；q2M读到至少一个0后，读到了至少一个1，并等待读更多的1；q3M读到至少一个0后跟至少一个1后，并且接着读到了至少一个2。,2023/10/15,26,先设计“主体框架”,再补充细节,当FA进入qt就无法离开此状态。qt相当于一个陷阱状态(trap)。一般将陷阱状态用作发现输入串不可能是该FA所识别的语言的句子时进入的状态。在此状态下，FA读完输入串中剩余的字符。,2023/10/15,27,例 构造一个DFA，它接受的语言为x|x0，1*，且当把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，即能被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状态。,2023/10/15,28,接受语言x|x0，1*，且当把x看成二进制数时，x模3与0同余的DFA如下：,0,1,0,0能被3整除,1,0,1模3余1,00能被3整除,01模3余1,10模3余2,0,1,11能被3整除,100模3余1,1,101模3余2,接受的语言是由一切含有偶数个0和偶数个1的字符串组成的集合。,确定有限自动机的程序设计,q=m_qqd,2023/10/15,31,3.3 不确定有限自动机,一个非确定的有限自动机(Nondeterministic Finite Automata)简记为NFA，是一个五元组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。,2023/10/15,32,希望是接受x|x0，1*，且x含有子串00或11的FA如下：,2023/10/15,33,希望是接受x|x0，1*，且x 的倒数第10个字符为1的FA如下：,2023/10/15,34,这两个图所给的“FA”与前面我们所定义的FA，即DFA，的区别在于：并不是对于所有的(q，a)Q,(q，a)都有一个状态与它对应；并不是对于所有的(q，a)Q,(q，a)只对应一个状态。“FA”在任意时刻可以处于有限多个状态。,2023/10/15,35,对于一个输入字符，NFA与DFA的差异是前者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从DFA看待问题的角度来说，NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的“总效果”相当于它处于这些状态对应的一个“综合状态”。因此，我们考虑让DFA用一个状态去对应NFA的一组状态。,2023/10/15,36,NFA与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。,2023/10/15,37,构造给定NFA等价的DFA策略先只把开始状态q0填入表的状态列中，如果表中所列的状态列有未处理的，则任选一个未处理的状态q1，q2，qn，对中的每个字符a，计算(q1，q2，qn，a)，并填入相应的表项中，如果(q1，q2，qn，a)在表的状态列未出现过，则将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。,从NFA构造等价的DFA更为实用的方法是采取以下步骤：从状态q0出发，通过状态转移函数，逐步扩充状态集；每一步仅对状态集中新增加的状态，才写出状态转移函数；此过程一直继续下去，直到不再增加新的状态为止，最后就得到了DFA。,第一步 从q0开始：(q0,0)=q0,q1,(q0,1)=q0,q2。第二步 处理两个新状态q0,q1和q0,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个状态。,2023/10/15,40,NFA的等价DFA,第一步 从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,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,q3,q4,q2,1)=q0,q1,q2,q4。到这一步为止，不再增加新的状态，所求的DFA只包含9个状态。,有限自动机的应用,在文本中查找字符串用于文本搜索识别关键字集合,在Web和其它在线文本库时代，一个常见的问题是，给定一个单词集合，查找包含一个（或全部）单词的所有文档。搜索引擎是完成这个任务的一个专门的软件，它对Web上出现的每个单词（大约有一亿种不同的英文单词），保存这个单词所有出现之处的列表。要用非常大的主存的计算机保持这些列表的最常见部分，以便随时可用，允许许多人在瞬间搜索这些文档。虽然在搜索引擎中常用的倒排索引技术没有使用有穷自动机，但有许多有关的应用不适合使用倒排索引,但很适合于应用基于自动机的技术。,适合应用自动机技术来搜索的特征是：所搜索的数据库快速变化。例如：（a）每一天，新闻分析员希望搜索当天在线的新闻文章来寻找有关话题。比如，金融分析员可能搜索他感兴趣的股票代码或公司名称。（b）“采购机器人”软件希望搜索顾客要求的商品的当前价格。“机器人”从Web上获得当前的目录页面，然后搜索这些页面寻找提示具体商品价格的单词。所搜索的文档不能建立目录。出于商业机密的考虑，有些公司（比如出版商）不愿意让人轻易发现本公司销售的所有书的所有页面。实际上，在响应查询的“一瞬间”才生成这些页面。,NFA,DFA,2023/10/15,49,3.4 带空移动的有限状态自动机,接受语言0n1m2k|n，m，k0的NFA,2023/10/15,50,接受语言0n1m2k|n，m，k0的NFA是否可以构造成下图所示的“-NFA”？,其构造显然比上图所示的NFA更容易。当然还希望它们是等价的。,它的函数是：(q0,0)=q0，(q1,1)=q1，(q2,2)=q2(q0,)=q1，(q1,)=q2，,2023/10/15,51,带空移动的不确定的有限状态自动机(non-deterministic finite automaton with-moves,-NFA)M=(Q，q0，F)，Q、q0、F的意义同DFA。：Q()2Q,2023/10/15,52,非空移动(q，a)Q(q，a)=p1，p2，pm表示M在状态q读入字符a，可以选择地将状态变成p1、p2、或者pm，并将读头向右移动一个带方格而指向输入字符串的下一个字符。,2023/10/15,53,空移动qQ(q，)=p1，p2，pm表示M在状态q不读入任何字符，可以选择地将状态变成p1、p2、或者pm。也可以叫做M在状态q做一个空移动(又可以称为移动)，并且选择地将状态变成p1、p2、或者pm。,2023/10/15,54,例,定理-NFA与NFA等价。,空闭包的定义 在一个有转移的有限穷自动机中，用-CLOSURE(q)表示状态q的空闭包，它是下述定义的状态集：(1)q在-CLOSURE(q)中；(2)若p在-CLOSURE(q)中，则(p,)也都在-CLOSURE(q)中；(3)重复(2)，直到-CLOSURE(q)中状态不再增加为止。从转移图上看，-CLOSURE(q)就是从状态q出发，沿着标有的有向边所能达到的一切状态所构成的集合（包括状态q本身）。,对于状态集P的-CLOSURE，-CLOSURE(P)=-CLOSURE(q)。,-CLOSURE(q0)=q0,q1,q2-CLOSURE(q1)=q1,q2。,扩充转移函数对于一个具有转移的有限穷自动机，它的扩充转移函数定义如下：(q,)=-CLOSURE(q),(q,wa)=-CLOSURE(P),P=(r,a)。其中qQ,a,w*。注意，扩充转移函数已经不是的简单扩充，与完全不相同。,带空移动的自动机转为不确定自动机,(q0,0)=-CLOSURE(q0,),0)=-CLOSURE(q0,q1,q2,0)=-CLOSURE(q0)=q0,q1,q2,与(q0,0)=q0不同,(q0,1)=-CLOSURE(q0,),1)=-CLOSURE(q0,q1,q2,1)=-CLOSURE(q1)=q1,q2,(q0,2)=-CLOSURE(q0,),2)=-CLOSURE(q0,q1,q2,2)=-CLOSURE(q2)=q2,(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)=q2,(q2,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)=q2,2023/10/15,63,3.5 带输出的FA,Moore机 M=(Q，q0)Q、q0、的意义同DFA。输出字母表(output alphabet)。：Q为输出函数。对qQ，(q)=a表示M在状态q时输出a。,输入的字符同时输出：(q0)=，(q1)=0，(q2)=1(q3)=0，(q4)=1，：(q0)=0|1，(q1)=0|1，(q2)=0|1(q3)=，(q4)=,例 设计一个Moore机，=0，1，若将输入串看成一个二进制数，要求在读入过程中，能输出它已读过子串的模3余数。因为模3余数只能有0，1，2三个值，因此取=0，1，2，并且只设三个状态q0,q1,q2，分别对应这三种余数。,2023/10/15,68,Mealy机 M=(Q，q0)输出字母表。：Q为输出函数。对(q，a)Q，(q，a)=d表示M在状态q读入字符a时输出d。,输入的字符同时输出：(q0，0)=0，(q0，1)=1，(q1，0)=0，(q1，1)=1，(q2，0)=0，(q2，1)=1，,例 给出一个0，1串的集合S，该集合中的串都以00或11结尾。要求设计一个只有两个输出符号（=y,n）的Mealy机，当它读过属于集合S的串时，输出y，表示接受；当它读过不属于集合S的串时，输出n，表示不接受。,2023/10/15,73,Moore机处理该串时每经过一个状态，就输出一个字符：输出字符和状态一一对应；Mealy机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。,转为Mealy机,