03 有穷状态自动机.ppt

《03 有穷状态自动机.ppt》由会员分享，可在线阅读，更多相关《03 有穷状态自动机.ppt（113页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1形式语言与自动机形式语言与自动机朴秀峰朴秀峰2主要内容主要内容q确定的有穷状态自动机确定的有穷状态自动机(DFA)作作为为对对实实际际问问题题的的抽抽象象、直直观观物物理理模模型型、形形式式定定义义，DFA接受的句子、语言，状态转移图。接受的句子、语言，状态转移图。q不确定的有穷状态自动机不确定的有穷状态自动机(NFA)定义、定义、NFA与与DFA的等价性。的等价性。q带空移动的有穷状态自动机带空移动的有穷状态自动机(-NFA)定义、定义、-NFA与与DFA的等价性。的等价性。qFA是正则语言的识别器是正则语言的识别器正正则则文文法法(RG)与与FA的的等等价价性性、相相互互转转换换方方法法

2、、带带输输出出的有穷状态自动机、双向有穷状态自动机。的有穷状态自动机、双向有穷状态自动机。33.1 语言的识别q给定一个正则文法给定一个正则文法G=(V,T,P,S)，即可确定，即可确定相应的正则语言相应的正则语言L(G)。q任给一个字符串任给一个字符串w，w 是否为是否为L(G)的句子？的句子？q即即S*w在在G 中是否成立？中是否成立？q推导和归约中的回溯问题将对系统的效率产生极大的影响推导和归约中的回溯问题将对系统的效率产生极大的影响SaA|aBAaA|cBaB|d分析句子分析句子aaac的过程中可能需要回溯。的过程中可能需要回溯。该文法识别的语言该文法识别的语言anc|n1and|n1

3、43.1语言的识别语言的识别 q系统识别语言系统识别语言anc|n1and|n1的字符串过程中状的字符串过程中状态的变化可以用下图表示：态的变化可以用下图表示：aaq0q1q2q3Scd5识别系统识别系统(模型模型)(1)系统具有有穷个状态，不同的状态代表不同的意义。系统具有有穷个状态，不同的状态代表不同的意义。按照按照实际的需要，系统可以在不同的状态下完成规定的任务。实际的需要，系统可以在不同的状态下完成规定的任务。(2)可以可以将输入字符串中出现的字符汇集在一起构成一个字母将输入字符串中出现的字符汇集在一起构成一个字母表表。系统处理的所有字符串都是这个字母表上的字符串。系统处理的所有字符串

4、都是这个字母表上的字符串。系统在任何一个状态系统在任何一个状态(当前状态当前状态)下，从输入字符串中读入下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态一个字符，根据当前状态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可以是不同的当前状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统再读时，会读入下一个字符。这就是说，相当于系统维持维持有一个读写指针有一个读写指针，该指针在系统读入一个字符后指向输入，该指针

5、在系统读入一个字符后指向输入串的下一个字符。串的下一个字符。6识别系统识别系统(模型模型)(4)系统中有一个状态，它是系统中有一个状态，它是系统的开始状态系统的开始状态，系统在这个状，系统在这个状态下开始进行某个给定句子的处理。态下开始进行某个给定句子的处理。(5)系统中还系统中还有一些状态表示它到目前为止所读入的字符构成有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子的字符串是语言的一个句子，把所有将系统从开始状态引，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。是系统所能识

6、别的语言。7有穷状态自动机的物理模型q相应的物理模型相应的物理模型一个右端无穷的输入带。一个右端无穷的输入带。一个有穷状态控制器一个有穷状态控制器(finitestatecontrol,FSC)。一个读头。一个读头。q系统的每一个动作由三个节拍构成系统的每一个动作由三个节拍构成读入读头正指向的字符；读入读头正指向的字符；根据当前状态和读入的字符改变有穷控制器的状态；根据当前状态和读入的字符改变有穷控制器的状态；将读头向右移动一格。将读头向右移动一格。83.2有穷状态自动机有穷状态自动机有穷状态自动机有穷状态自动机(finiteautomaton,FA)是一个五元组：是一个五元组：M=(Q,q0

7、,F)Q状状态态的的非非空空有有穷穷集集合合。qQ，q称称为为M的的一一个个状状态态(state)。输入字母表输入字母表(Inputalphabet)。输入字符串都是。输入字符串都是上的字上的字符串。符串。状状态态转转移移函函数数(transitionfunction)，有有时时又又叫叫做做状状态态转转换换函函数数或或者者移移动动函函数数，:QQ。对对(q,a)Q，(q,a)=p表表示示M在在状状态态q读读入入字字符符a，将将状状态态变变成成p，并并将将读读头头向向右右移移动一个带方格而指向输入字符串的下一个字符。动一个带方格而指向输入字符串的下一个字符。q0q0Q，是是M的的开开始始状状态态

8、(initialstate)，也也可可叫叫做做初初始始状状态态或者或者启动状态启动状态。FF Q，是，是M的的终止状态终止状态(finalstate)集合集合。qF，q称为称为M的的终止状态终止状态，又称为，又称为接受状态接受状态(acceptstate)。9例3-1下面是一个有穷状态自动机下面是一个有穷状态自动机M1=(q0,q1,q2,0,1,q0,q2)其中，其中，1(q0,0)=q1,1(q1,0)=q2,1(q2,0)=q1用表用表3-1表示表示1。状态说明状态说明状态状态输入字符输入字符0开始状态开始状态q0q1q1q2终止状态终止状态q2q110例3-1M2=(q0,q1,q2,

9、q3，0,1,2，2，q0，q2)2(q0,0)=q1，2(q1,0)=q2，2(q2,0)=q1，2(q3,0)=q32(q0,1)=q3，2(q1,1)=q3，2(q2,1)=q3，2(q3,1)=q32(q0,2)=q3，2(q1,2)=q3，2(q2,2)=q3，2(q3,2)=q3状态说明状态说明状态状态输入字符输入字符012开始状态开始状态q0q1q3q3q1q2q3q3终止状态终止状态q2q1q3q3q3q3q3q3表表3-2 2转换函数转换函数11扩展的状态转移函数将将扩充为扩充为对任意的对任意的qQ，w*，a，定义，定义两值相同，不用区分这两个符号。两值相同，不用区分这两个符

10、号。12确定的有穷状态自动机(DFA)q对于任意的对于任意的qQ，a，(q,a)均有确定的值，均有确定的值，所以，将这种所以，将这种FA称为称为确定的有穷状态自动机确定的有穷状态自动机(deterministicfiniteautomaton，DFA)13M接受(识别)的语言q能引导能引导FA从启动状态出发，最终到达终止状态的字符串从启动状态出发，最终到达终止状态的字符串是是FA识别的语言的句子。识别的语言的句子。q所有这样的字符串组成的集合为所有这样的字符串组成的集合为FAM 接受的语言。接受的语言。q对于对于 x*，如果，如果(q0,x)F，则称，则称x被被M接受接受，如果，如果(q0,w

11、)F，则称，则称M不接受不接受x。L(M)=x|x*且且(q0,x)F称为由称为由M接受接受(识别识别)的语言的语言。q例例3-1中，中，L(M1)=L(M2)=02n|n1q如果如果L(M1)=L(M2)，则称，则称M1与与M2等价。等价。14例3-2构造一个构造一个DFA，它接受的语言为，它接受的语言为x000y|x,y0,1*。关键：是否出现了子串关键：是否出现了子串“000”？q0M的启动状态；的启动状态；q1M读读到到了了一一个个0，这这个个0可可能能是是子子串串“000”的的第第1个个0；q2M在在q1后后紧紧接接着着又又读读到到了了一一个个0，这这个个0可可能能是是子子串串“00

12、0”的第的第2个个0；q3M在在q2后后紧紧接接着着又又读读到到了了一一个个0，发发现现输输入入字字符符串串含含有子串有子串“000”；因此，这个状态应该是终止状态。；因此，这个状态应该是终止状态。可以给出可以给出M的状态转移函数的部分定义：的状态转移函数的部分定义：(q0,0)=q1M读读到到了了一一个个0，这这个个0可可能能是是子子串串“000”的的第第1个个0。(q1,0)=q2M 又又读读到到了了一一个个 0，这这个个 0 可可能能是是子子串串“000”的第的第2个个0。(q2,0)=q3M找到了子串找到了子串“000”。15例3-2(q0,1)=q0M 在在q0读读到到了了一一个个1

13、，它它需需要要继继续续在在q0“等等待待”可能是子串可能是子串“000”的第的第1个个0的输入字符的输入字符0；(q1,1)=q0M在在刚刚刚刚读读到到了了一一个个0后后，读读到到了了一一个个1，表表明明在在读读入入这这个个1之之前前所所读读入入的的0并并不不是是子子串串“000”的的第第1个个0，因因此此，M需需要要重重新新回回到到状状态态q0，以以寻寻找找子子串串“000”的的第第1个个0；(q2,1)=q0M在在刚刚刚刚发发现现了了00后后，读读到到了了一一个个1，表表明明在在读读入入这这个个1之之前前所所读读入入的的00并并不不是是子子串串“000”的的前前两两个个0，因因此此，M需要

14、重新回到状态需要重新回到状态q0，以寻找子串，以寻找子串“000”的第的第1个个0；(q3,0)=q3M找到了子串找到了子串“000”，只用读入该串的剩余部分。，只用读入该串的剩余部分。(q3,1)=q3M 找找到到了了子子串串“000”，只只用用读读入入该该串串的的剩剩余余部部分分。16例3-2M=(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)状态说明状态说明状态状态输入字符输入字符01开始状态开始状态q0q1q0q1q2q0q2q3

15、q0终止状态终止状态q3q3q317例3-2一种更为直观的表示一种更为直观的表示0010q3q0q1q20,11S18状态转移图状态转移图q状态转移图状态转移图(transitiondiagram)(1)qQq 是该有向图中的一个顶点；是该有向图中的一个顶点；(2)(q,a)=p图中有一条从顶点图中有一条从顶点q 到顶点到顶点p 的标记为的标记为a 的弧；的弧；(3)qF标记为标记为q 的顶点被用的顶点被用双层圈双层圈标出；标出；(4)用标有用标有S 的箭头指出的箭头指出M的开始状态。的开始状态。q状态转移图又可以叫做状态转移图又可以叫做状态转换图状态转换图。0010q3q0q1q20,11S

16、19例3-3 构造一个构造一个DFA，它接受的语言为，它接受的语言为x000|x0,1*。qq0读到的读到的0可能是输入字符串的最后三个可能是输入字符串的最后三个0的第的第1个个0；qq1读到的读到的0可能是输入字符串的最后三个可能是输入字符串的最后三个0的第的第2个个0；qq2读到的读到的0可能是输入字符串的最后三个可能是输入字符串的最后三个0的第的第3个个0；qq3读到的读到的0也可能是输入字符串的最后三个也可能是输入字符串的最后三个0的第的第3个个0；q如如果果在在状状态态q1,q2,q3读读到到的的是是1，则则要要重重新新检检查查输输入入串串是是否否以以三个三个0结尾。结尾。0010q

17、3q0q1q2110S120例3-3的说明(1)定义定义FA时，常常只给出时，常常只给出FA相应的状态转移图即可。相应的状态转移图即可。(2)对于对于DFA来说，每个顶点的出度恰好等于输入字母表中来说，每个顶点的出度恰好等于输入字母表中所含的字符的个数。所含的字符的个数。(3)字符串字符串x 被被FAM接受的充分必要条件是，在接受的充分必要条件是，在M的状态转的状态转移图中存在一条从开始状态到某一个终止状态的有向路，移图中存在一条从开始状态到某一个终止状态的有向路，该有向路上从第该有向路上从第1条边到最后一条边的标记依次并置而构条边到最后一条边的标记依次并置而构成的字符串成的字符串x。简称此路

18、的标记为。简称此路的标记为x。(4)一个一个FA有且只有有且只有一个初始状态。一个初始状态。(5)一个一个FA可以有多个接受状态。可以有多个接受状态。21举例举例接受语言接受语言x000|x0,1*x001|x0,1*的的FA。22即时描述 q问题：如何在一维空间直观地描述有穷自动机的状况？问题：如何在一维空间直观地描述有穷自动机的状况？q即时描述即时描述(instantaneousdescription，ID）x,y*，(q0,x)=q,xqy 称为称为M的一个的一个即时描述即时描述，xy是是M 正在处理的一个字符串正在处理的一个字符串x 引导引导M从从q0启动并到达状态启动并到达状态qM的

19、读头当前正指向的读头当前正指向y的首字符的首字符q如果如果xqay是是M的一个即时描述，且的一个即时描述，且(q,a)=p，则，则xqayMxapy表示表示M在状态在状态q时已经处理完时已经处理完x并且读头正指向输入字符并且读头正指向输入字符a，此时它读入，此时它读入a并转入状态并转入状态p，将读头向右移动一个指向，将读头向右移动一个指向y的首字符。的首字符。23即时描述转换qMn：表示：表示M从即时描述从即时描述经过经过 n次移动到达即时描述次移动到达即时描述。即即M存在即时描述存在即时描述1,2,n-1,使得使得M1,1M2,n-1M当当n=0时，有时，有=。即。即M0。qM+：表表示示

20、M 从从即即时时描描述述经经过过至至少少1次次移移动动到到达达即即时时描描述述。qM*：表示：表示M 从即时描述从即时描述经过经过若干若干步移动到达即时描述步移动到达即时描述。q当意义清楚时，将符号当意义清楚时，将符号M、Mn、M*、M+中的中的 M省省去，分别用去，分别用、n、*、+表示。表示。24即时描述举例 用下图所定义的用下图所定义的M处理输入串处理输入串1010010001。q010100100011q001001000110q110010001101q000100011010q101000110100q210001101001q000011010010q100110100100q2

21、01101001000q31 1010010001q0即即q01010010001101010010001q0q01010010001+1010010001q0q01010010001*1010010001q00010q3q0q1q2110S125即时描述 q对于对于 x*,q0 x1+x1q0q0 x10+x10q1q0 x100+x100q2q0 x000+x000q30010q3q0q1q2110S126set(q)能引导能引导 FA从开始状态到达从开始状态到达 q的字符串的集合为：的字符串的集合为：set(q)=x|x*，(q0,x)=q举例：对下图所给的举例：对下图所给的 DFA中的

22、所有中的所有q，求，求set(q)。set(q0)=x|x*，x=或者或者 x以以 1结尾结尾set(q1)=x|x*，x=0或者或者 x以以 10结尾结尾set(q2)=x|x*，x=00或者或者 x 以以 100结尾结尾set(q3)=x|x*，x 以以 000结尾结尾set(q4)=x|x*，x 以以 001结尾结尾这这5个集合是两两互不相交。个集合是两两互不相交。27DFA上的等价关系q对对于于任任意意一一个个FAM=(Q,q0,F)，可可以以按按照照如如下下方方式式定定义关系义关系RM：对对 x,y*，xRMy qQ，使使得得xset(q)和和yset(q)同时成立。同时成立。q按照

23、这个定义所得到的关系实际上是按照这个定义所得到的关系实际上是*上的一个等价关系。上的一个等价关系。利用这个关系，可以利用这个关系，可以将将*划分成不多于划分成不多于|Q|个等价类个等价类。28例3-4 构造一个构造一个DFA，它接受的语言为，它接受的语言为0n1m2k|n,m,k1。q0M的启动状态；的启动状态；q1M读到至少一个读到至少一个0，并等待读更多的，并等待读更多的0；q2M读读到到至至少少一一个个0后后，读读到到了了至至少少一一个个1，并并等等待待读读更更多的多的1；q3M读到至少一个读到至少一个0后跟至少一个后跟至少一个1后，并且接着读到后，并且接着读到了至少一个了至少一个2。2

24、9例3-4先设计先设计“主体框架主体框架”再补充细节再补充细节30例3-4的启示当当FA一旦进入状态一旦进入状态 qt，它就无法离开此状态。所以，它就无法离开此状态。所以，qt 相相当于一个当于一个陷阱状态陷阱状态(trap)。一般地，我们。一般地，我们将陷阱状态用作在将陷阱状态用作在其他状态下发现输入串不可能是该其他状态下发现输入串不可能是该FA所识别的语言的句子时所识别的语言的句子时进入的状态进入的状态。在此状态下，。在此状态下，FA读完输入串中剩余的字符。读完输入串中剩余的字符。在构造一个识别给定语言的在构造一个识别给定语言的FA时，用画图的方式比较方便、时，用画图的方式比较方便、直观。

25、我们可以先直观。我们可以先根据语言的主要特征画出该根据语言的主要特征画出该FA的的“主体主体框架框架”，然后再去考虑画出一些细节要求的内容。，然后再去考虑画出一些细节要求的内容。FA的状态具有一定的记忆功能的状态具有一定的记忆功能：不同的状态对应于不同的：不同的状态对应于不同的情况，由于情况，由于FA只有有穷个状态，所以，在识别一个语言的只有有穷个状态，所以，在识别一个语言的过程中，如果有无穷种情况需要记忆，我们肯定是无法构造过程中，如果有无穷种情况需要记忆，我们肯定是无法构造出相应的出相应的FA的。的。比如语言比如语言0n1n|n1。31例例3-5构造一个构造一个DFA，它接受的语言为，它接

26、受的语言为x|x0,1*，且当把，且当把x看看成二进制数时，成二进制数时，x模模3与与0同余同余。qqsM的开始状态。的开始状态。qq0对应除以对应除以3余数为余数为0的的x组成的等价类；组成的等价类；qq1对应除以对应除以3余数为余数为1的的x组成的等价类；组成的等价类；qq2对应除以对应除以3余数为余数为2的的x组成的等价类。组成的等价类。qs读入读入0时，有时，有x=0，所以应该进入状态，所以应该进入状态q0；读入读入1时，有时，有x=1，所以应该进入状态，所以应该进入状态q1。即即(qs,0)=q0；(qs,1)=q1。32例例3-5构造一个构造一个DFA，它接受的语言为，它接受的语言

27、为x|x0,1*，且当把，且当把x看看成二进制数时，成二进制数时，x模模3与与0同余同余。qqsM的开始状态。的开始状态。qq0对应除以对应除以3余数为余数为0的的x组成的等价类；组成的等价类；qq1对应除以对应除以3余数为余数为1的的x组成的等价类；组成的等价类；qq2对应除以对应除以3余数为余数为2的的x组成的等价类。组成的等价类。qq0能引导能引导M到达此状态的到达此状态的x除以除以3余余0所以有：所以有：x=3*n+0。读读 入入 0时时，引引 导导 M到到 达达 下下 一一 个个 状状 态态 的的 字字 符符 串串 为为 x0，x0=2*(3*n+0)=3*2*n+0。所以，。所以，

28、(q0,0)=q0；读入读入1时，时，M到达下一个状态的字符串为到达下一个状态的字符串为x1，x1=2*(3*n+0)+1=3*2*n+1。所以，。所以，(q0,1)=q1。33例例3-5构造一个构造一个DFA，它接受的语言为，它接受的语言为x|x0,1*，且当把，且当把x看看成二进制数时，成二进制数时，x模模3与与0同余同余。qqsM的开始状态。的开始状态。qq0对应除以对应除以3余数为余数为0的的x组成的等价类；组成的等价类；qq1对应除以对应除以3余数为余数为1的的x组成的等价类；组成的等价类；qq2对应除以对应除以3余数为余数为2的的x组成的等价类。组成的等价类。qq1能引导能引导 M

29、 到达此状态的到达此状态的 x 除以除以3余余1所以有所以有 x=3*n+1。读读 入入 0时时，引引 导导 M到到 达达 下下 一一 个个 状状 态态 的的 字字 符符 串串 为为 x0，x0=2*(3*n+1)=3*2*n+2。所以。所以(q1,0)=q2；读入读入1时，引导时，引导 M到达下一个状态的字符串为到达下一个状态的字符串为 x1，x1=2*(3*n+1)+1=3*2*n+2+1=3*(2*n+1)。所以。所以(q1,1)=q034例例3-5构造一个构造一个DFA，它接受的语言为，它接受的语言为x|x0,1*，且当把，且当把x看看成二进制数时，成二进制数时，x模模3与与0同余同余

30、。qqsM的开始状态。的开始状态。qq0对应除以对应除以3余数为余数为0的的x组成的等价类；组成的等价类；qq1对应除以对应除以3余数为余数为1的的x组成的等价类；组成的等价类；qq2对应除以对应除以3余数为余数为2的的x组成的等价类。组成的等价类。qq2能引导能引导 M到达此状态的到达此状态的 x 除以除以3余余2，所以所以 x=3*n+2。读读 入入 0时时，引引 导导 M到到 达达 下下 一一 个个 状状 态态 的的 字字 符符 串串 为为 x0，x0=2*(3*n+2)=3*2*n+4=3*(2*n+1)+1。所以。所以(q2,0)=q1；读入读入1时，引导时，引导M到达下一个状态的字

31、符串为到达下一个状态的字符串为x1，x1=2*(3*n+2)+1=3*2*n+4+1=3*(2*n+1)+2。所以所以(q2,1)=q2。35例例3-5接受语言接受语言x|x0,1*，且当把，且当把x看成二进制数时，看成二进制数时，x模模3与与0同余同余的的DFA如下：如下：要点：将等价类（同余类）与状态对应起来。要点：将等价类（同余类）与状态对应起来。36例3-6构造一个构造一个DFA，它接受的语言，它接受的语言L=x|x0,1*，且对，且对x中任中任意一个长度不大于意一个长度不大于5的子串的子串a1a2an,a1+a2+an3，n5。输入串为输入串为a1a2aiai+4ai+5am37例3

32、-6q当当i=1,2,3，也就是，也就是M读到输入串的第读到输入串的第1,2,3个字符时，它需个字符时，它需要将这些字符记下来。因为要将这些字符记下来。因为a1ai可能需要用来判定输入可能需要用来判定输入串的最初串的最初45个字符组成的子串是否满足语言的要求。个字符组成的子串是否满足语言的要求。q当当i=4,5，也就是，也就是M读到输入串的第读到输入串的第4,5个字符时，个字符时，在在a1+a2+ai3的情况下，的情况下，M需要将需要将a1ai记下来；记下来；在在a1+a2+ai3时，时，M应该进入陷阱状态应该进入陷阱状态qt。q当当i=6，也就是，也就是M读到输入串的第读到输入串的第6个字符

33、，此时，以前读个字符，此时，以前读到的第到的第1个字符个字符a1就没有用了，此时它要看就没有用了，此时它要看a2+a3+a63是否成立，如果成立，是否成立，如果成立，M需要将需要将a2a6记下来；在记下来；在a2+a3+ai3时，时，M应该进入陷阱状态应该进入陷阱状态qt。38例3-6q当当M完成对子串完成对子串a1a2aiai+4的考察，并发现它满足语言的的考察，并发现它满足语言的要求时，要求时，M记下来的是记下来的是aiai+4，此时它读入输入串的第，此时它读入输入串的第i+5个字符个字符ai+5，以前读到的第，以前读到的第i个字符个字符ai就没有用了，此时它要就没有用了，此时它要看看ai

34、+1+ai+2+ai+53是否成立，如果成立，是否成立，如果成立，M需要将需要将ai+1，ai+2，ai+5记下来；在记下来；在ai+1+ai+2+ai+53时，时，M应该进入应该进入陷阱状态陷阱状态qt。39例3-6qM需要记忆的内容有：需要记忆的内容有：什么都未读入什么都未读入20=1种；种；记录有记录有1个字符个字符21=2种；种；记录有记录有2个字符个字符22=4种；种；记录有记录有3个字符个字符23=8种；种；记录有记录有4个字符个字符24-1=15种；种；记录有记录有5个字符个字符25-6=26种；种；记录当前的输入串不是句子记录当前的输入串不是句子1种。种。q问题：难以对每个状态

35、命名问题：难以对每个状态命名qC语言中变量多到难以命名时如何处理？语言中变量多到难以命名时如何处理？40例3-6状态设置状态设置qM还未读入任何字符；还未读入任何字符；qt陷阱状态；陷阱状态；qa1a2aiM记录有记录有i个字符，个字符，1i5。a1,a2,ai0,1。取取DFAM=(Q,0,1,q,F)F=qqa1a2ai|a1,a2,ai0,1且且1i5且且a1+a2+ai3Q=qtF41例3-6(q,a1)=qa1(qa1,a2)=qa1a2(qa1a2,a3)=qa1a2a3(qa1a2a3,a)=qa1a2a3a如果如果a1+a2+a3+a3qt如果如果a1+a2+a3+a3(qa1

36、a2a3a4,a)=qa1a2a3a4a如果如果a1+a2+a3+a4+a3qt如果如果a1+a2+a3+a4+a3(qa1a2a3a4a5,a)=qa2a3a4a5a如果如果a2+a3+a4+a5+a3qt如果如果a2+a3+a4+a5+a3(qt,a1)=qt要点：将要记忆的内容用作对状态的标识。要点：将要记忆的内容用作对状态的标识。42问题问题q考虑接受考虑接受x|x0,1*，且，且x含有子串含有子串00或或11的的DFA。00q3q0q10,1S11q4q30,101q接受接受x|x0,1*，且，且x的倒数第的倒数第10个字符为个字符为1的的DFA？qDFA通常比较复杂！通常比较复杂！

37、433.3不确定的有穷状态自动机不确定的有穷状态自动机考虑对考虑对DFA的修改的修改q希望是接受希望是接受x|x0,1*，且，且x含有子串含有子串00或或11的的FA如下：如下：q接受接受x|x0,1*，且，且x的倒数第的倒数第10个字符为个字符为1的的FA如下如下：00q0q1S11q3q20,10,144作为对 DFA 的修改q这这两两个个图图所所给给的的“FA”与与前前面面我我们们所所定定义义的的FA(即即DFA)的区别在于：的区别在于：并并不不是是对对于于所所有有的的(q,a)Q,(q,a)都都有有一一个个状状态态与与它对应；它对应；并不是对于所有的并不是对于所有的(q,a)Q,(q,

38、a)只对应一个状态。只对应一个状态。qQ的有穷性保证了的有穷性保证了2Q的有穷性。的有穷性。q“FA”在任意时刻可以处于有穷多个状态。在任意时刻可以处于有穷多个状态。q“FA”具有具有“智能智能”。45不能继续不能继续不能继续不能继续接受所有以 01 结尾的串的 NFA 的工作过程在处理输入序列在处理输入序列00101时时NFA所处的状态：所处的状态：0,1q0q1q201sq00q0q00q01q00q01q1q1q2q1q246NFA的形式定义的形式定义不不确确定定的的有有穷穷状状态态自自动动机机(non-deterministicfiniteautomaton,NFA)M是一个五元组：是

39、一个五元组：M=(Q,q0,F)Q,q0,F的意义同的意义同DFA。:Q2Q，对对(q,a)Q，(q,a)=p1,p2,pm表表示示M在在状状态态q 读读入入字字符符a，可可以以选选择择地地将将状状态态变变成成p1,p2,或或者者pm，并并将将读读头头向向右右移移动动一一个个带带方方格格而而指指向向输输入入字字符符串串的的下下一一个个字符。字符。FA的状态转移图、的状态转移图、FA的状态对应的等价类、的状态对应的等价类、FA的即时的即时描述对描述对NFA都有效。都有效。47NFA举例举例q接受接受x|x0,1*，且，且x含有子串含有子串00或或11的的NFA对应的对应的状态转移函数定义表。状态

40、转移函数定义表。状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0,q1q0,q2q1q3q2q3终止状态终止状态q3q3q300q0q1S11q3q20,10,148NFA的举例的举例q接受接受x|x0,1*，且，且x的倒数第的倒数第10个字符为个字符为1的的FA对应的对应的移动函数定义表。移动函数定义表。状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0q0,q1q1q2q2q2q3q3q3q4q4q4q5q5q5q6q6q6q7q7q7q8q8q8q9q9q9q10q10终止状态终止状态q1049扩展转移函数扩展转移函数将将扩充为扩充为对任意的对任意的

41、 qQ，w*，a，定义，定义 和关于和关于DFA的结论一样，两值相同，也不用区分这两个符号。的结论一样，两值相同，也不用区分这两个符号。50扩展转移函数扩展转移函数进一步扩充进一步扩充定义域：定义域：:2Q*2Q。对任意的对任意的P Q,w*由于，对由于，对 (q,w)Q*所以，不一定严格地区分所以，不一定严格地区分的第的第1个分量是一个状态还是一个个分量是一个状态还是一个含有一个元素的集合。含有一个元素的集合。51扩展转移函数扩展转移函数q对任意的对任意的qQ，w*，a：(q,wa)=(q,w),a)q对输入字符串对输入字符串a1a2an(q,a1a2an)=(q,a1),a2)，),an)

42、。52M接受接受(识别识别)的语言的语言对于对于 x*，如果如果(q0,w)F，则称，则称 x 被被 M 接受接受，如果如果(q0,w)F=，则称，则称 M 不接受不接受 x。L(M)=x|x*且且(q0,w)F称为称为由由 M接受接受(识别识别)的语言的语言。53NFA 与 DFA 等价 q对于一个输入字符，对于一个输入字符，NFA与与DFA的差异：的差异：NFA可以可以进入若干个状态进入若干个状态DFA只能只能进入一个惟一的状态进入一个惟一的状态。q虽然从虽然从DFA看待问题的角度来说，看待问题的角度来说，NFA在某一时刻同时进在某一时刻同时进入若干个状态，但是，这入若干个状态，但是，这若

43、干个状态合在一起的若干个状态合在一起的“总效果总效果”相当于它处于这些状态对应的一个相当于它处于这些状态对应的一个“综合状态综合状态”。q因此，考虑因此，考虑让让DFA用一个状态去对应用一个状态去对应NFA的一组状态的一组状态。NFA 与 DFA 等价 541q1q2q3q511q1q2,q3,q5q11q2q3q511q4112q033q1,q4q03q2,q3,q5q51255NFA与与DFA等价等价 qNFAM1=(Q,1,q0,F1)与与DFAM2=(Q2,2,q0,F2)的对的对应关系：应关系：NFA从从开始状态开始状态q0启动，启动，就让相应的就让相应的DFA从从状态状态q0启动。

44、所以启动。所以q0=q0。对于对于NFA的一个的一个状态组状态组q1,q2,qn，如果如果NFA在此状态组时读入字符在此状态组时读入字符a后可以进入状态组后可以进入状态组p1,p2,pm,则让相应的则让相应的DFA在在状态状态q1,q2,qn读入字符读入字符a时，时，进入状态进入状态p1,p2,pm。56NFA 与 DFA 等价 定理定理3-1NFA与与DFA等价。等价。证明思路：只需证明对于任给的证明思路：只需证明对于任给的NFA，存在与之等价的，存在与之等价的DFA。(1)构造模拟器构造模拟器构造与构造与NFAM1等价的等价的DFAM2。(2)进行辅助证明进行辅助证明1(q0,x)=p1,

45、p2,pm2(q0,x)=p1,p2,pm。(3)证明等价性证明等价性L(M1)=L(M2)57NFA 与 DFA 等价(1)构造与构造与NFAM1等价的等价的DFAM2。M1=(Q,1,q0,F1)M2=(Q2,2,q0,F2)Q2=2QF2=p1,p2,pm|p1,p2,pm Q且且p1,p2,pmF12(q1,q2,qn,a)=p1,p2,pm1(q1,q2,qn,a)=p1,p2,pm 58NFA 与 DFA 等价(2)证明证明1(q0,x)=p1,p2,pm2(q0,x)=p1,p2,pm。设设x*，施归纳于，施归纳于|x|:当当x=时，时，1(q0,)=q0,2(q0,)=q0同时

46、成立。同时成立。设当设当|x|=n 时结论成立。时结论成立。下面证明当下面证明当|x|=n+1时结论也成立。时结论也成立。不妨设不妨设x=wa，|w|=n，a1(q0,wa)=1(1(q0,w),a)=1(q1,q2,qn,a)=p1,p2,pm 由归纳假设，由归纳假设，1(q0,w)=q1,q2,qn2(q0,w)=q1,q2,qn59NFA 与 DFA 等价 根据根据2的定义，的定义，2(q1,q2,qn,a)=p1,p2,pm1(q1,q2,qn,a)=p1,p2,pm 所以，所以，2(q0,wa)=2(2(q0,w),a)=2(q1,q2,qn,a)=p1,p2,pm故，故，如果如果1

47、(q0,wa)=p1,p2,pm，则必有则必有2(q0,wa)=p1,p2,pm。由上述推导可知，反向的推导也成立。由上述推导可知，反向的推导也成立。这就是说，结论对这就是说，结论对|x|=n+1也成立。也成立。由归纳法原理，结论对由归纳法原理，结论对 x*成立。成立。60NFA 与 DFA 等价(3)证明证明 L(M1)=L(M2)设设 xL(M1)，且，且1(q0,x)=p1,p2,pm，从而从而1(q0,x)F1,这就是说，这就是说，p1,p2,pm F1，由由 F2的定义，的定义，p1,p2,pmF2。再由再由(2)知，知，2(q0,x)=p1,p2,pm 所以，所以，xL(M2)。故

48、。故 L(M1)L(M2)。反过来推，可得反过来推，可得 L(M2)L(M1)。从而从而 L(M1)=L(M2)得证。得证。综上所述，定理成立。综上所述，定理成立。61NFA 对应的DFA的状态转移函数举例 例例3-7下下图所示的图所示的NFA对应的对应的DFA的状态转移函数如表的状态转移函数如表3-7所所示。示。00q0q1S11q3q20,10,162表3-7 状态转移函数状态说明状态说明状态状态输入字符输入字符01启动启动 q0q0,q1q0,q2q1q3q2q3终止终止q3q3q3 q0,q1q0,q1,q3q0,q2 q0,q2q0,q1q0,q2,q3终止终止q0,q3q0,q1,

49、q3q0,q2,q3q1,q2q3q3终止终止q1,q3q3q3终止终止q2,q3q3q3q0,q1,q2q0,q1,q3q0,q2,q3终止终止 q0,q1,q3q0,q1,q3q0,q2,q3终止终止 q0,q2,q3q0,q1,q3q0,q2,q3终止终止q1,q2,q3q3q3终止终止q0,q1,q2,q3q0,q1,q3q0,q2,q363NFA与与DFA等价等价 q不可达状态不可达状态(inaccessiblestate)：不存在从：不存在从q0对应的顶点对应的顶点出发，到达该状态对应的顶点的路。出发，到达该状态对应的顶点的路。q构造给定构造给定NFA等价的等价的DFA策略策略把开

50、始状态把开始状态q0填入表的状态列中。填入表的状态列中。如果表中所列的状态列有未处理的，则任选一个未处理如果表中所列的状态列有未处理的，则任选一个未处理的状态的状态q1,q2,qn，对，对中的每个字符中的每个字符a，计算，计算(q1,q2,qn,a)，并填入相应的表项中，如果，并填入相应的表项中，如果(q1,q2,qn,a)在表的状态列未出现过，则将它填入表的状在表的状态列未出现过，则将它填入表的状态列。态列。如此重复下去，直到表的状态列中不存在未处理的状态。如此重复下去，直到表的状态列中不存在未处理的状态。64构造给定NFA等价的DFA状态说明状态说明状态状态输入字符输入字符01开始状态开始