形式语言与自动机理论电子教案-03.ppt

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

1、第第3章章有穷状态自动机有穷状态自动机主要内容主要内容确定的有穷状态自动机确定的有穷状态自动机(DFA)作作为为对对实实际际问问题题的的抽抽象象、直直观观物物理理模模型型、形形式式定义，定义，DFA接受的句子、语言，状态转移图。接受的句子、语言，状态转移图。不确定的有穷状态自动机不确定的有穷状态自动机(NFA)定义；定义；NFA与与DFA的等价性；的等价性；12/18/20221第第3章章有穷状态自动机有穷状态自动机带空移动的有穷状态自动机带空移动的有穷状态自动机(-NFA)定义。定义。-NFA与与DFA的等价性。的等价性。FA是正则语言的识别器是正则语言的识别器正则文法正则文法(RG)与与F

2、A的等价性。的等价性。相互转换方法。相互转换方法。带输出的有穷状态自动机。带输出的有穷状态自动机。双向有穷状态自动机。双向有穷状态自动机。12/18/20222第第3章章有穷状态自动机有穷状态自动机重重点点：DFA的的概概念念，DFA、NFA、-NFA、RG之间的等价转换思路与方法。之间的等价转换思路与方法。难难点点：对对DFA概概念念的的理理解解，DFA、RG的的构构造方法，造方法，RG与与FA的等价性证明。的等价性证明。12/18/202233.1 3.1 语言的识别语言的识别 推导和归约中的回溯问题将对系统的效率产推导和归约中的回溯问题将对系统的效率产生极大的影响生极大的影响 SaA|a

3、BAaA|cBaB|d分析句子分析句子aaac 的过程中可能需要回溯。的过程中可能需要回溯。12/18/202243.1 3.1 语言的识别语言的识别 系统识别语言系统识别语言anc|n1and|n1的字符的字符串过程中状态的变化图示如下：串过程中状态的变化图示如下：12/18/202253.1 3.1 语言的识别语言的识别识别系统识别系统(模型模型)系统具有有穷个状态，不同的状态代表系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。在不同的状态下完成规定的任务。我们可以将输入字符串中出现的字符汇我们可以将输

4、入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。有字符串都是这个字母表上的字符串。12/18/202263.1 3.1 语言的识别语言的识别系统在任何一个状态系统在任何一个状态(当前状态当前状态)下，从下，从输入字符串中读入一个字符，根据当前状输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次

5、再读时，会读读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。个字符后指向输入串的下一个字符。12/18/202273.1 3.1 语言的识别语言的识别系统中有一个状态，它是系统的开始状系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定态，系统在这个状态下开始进行某个给定句子的处理。句子的处理。系统中还有一些状态表示它到目前为止系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个所读入的字符构成的

6、字符串是语言的一个句子，把所有将系统从开始状态引导到这句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。该语言就是系统所能识别的语言。12/18/202283.1 3.1 语言的识别语言的识别相应的物理模型相应的物理模型一个右端无穷的输入带。一个右端无穷的输入带。一个有穷状态控制器一个有穷状态控制器(finite state(finite state control,FSC)control,FSC)。一个读头。一个读头。系统的每一个动作由三个节拍构成：读入系统的每一个动作由三个节拍构成：读入读头正注视的字符

7、；根据当前状态和读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头向的字符改变有穷控制器的状态；将读头向右移动一格。右移动一格。12/18/202293.1 3.1 语言的识别语言的识别 有穷状态自动机的物理模型有穷状态自动机的物理模型 12/18/2022103.23.2有穷状态自动机有穷状态自动机 有穷状态自动机有穷状态自动机(finite automaton,FA)(finite automaton,FA)M=(Q，q0，F)Q状状态态的的非非空空有有穷穷集集合合。qQ，q称称为为M的一个的一个状态状态(state)。输入字母表输入字母表(Input alphab

8、et)(Input alphabet)。输入字。输入字符串都是符串都是上的字符串。上的字符串。q0q0Q，是是M的的开开始始状状态态(initialstate)，也可叫做初始状态或者启动状态。，也可叫做初始状态或者启动状态。12/18/2022113.23.2有穷状态自动机有穷状态自动机 状态状态转移函数转移函数(transition function)(transition function)，有时候又叫做状态转换函数或者移动函数。有时候又叫做状态转换函数或者移动函数。：QQ，对，对(q，a)Q，(q，a)=p表示：表示：M在状态在状态q读入字符读入字符a，将状态变，将状态变成成p，并将读头

9、向右移动一个带方格而指向，并将读头向右移动一个带方格而指向输入字符串的下一个字符。输入字符串的下一个字符。FF Q，是，是M的的终止状态终止状态(final state)(final state)集合。集合。qF，q称为称为M的的终止状态，终止状态，又称又称为为接受状态接受状态(accept state)(accept state)。12/18/2022123.23.2有穷状态自动机有穷状态自动机 例例 3-1 3-1 下面是一个有穷状态自动机下面是一个有穷状态自动机 M1=(q0，q1，q2，0，1，q0，q2)其中，其中，1(q0,0)=q1，1(q1,0)=q2，1(q2,0)=q1 用

10、表用表3-1表示表示1。状态说明状态说明状态状态输入字符输入字符0开始状态开始状态q0q1q1q2终止状态终止状态q2q112/18/2022133.23.2有穷状态自动机有穷状态自动机 M2=(q0，q1，q2，q3，0，1，2，2，q0，q2)2(q0,0)=q1，2(q1,0)=q22(q2,0)=q1，2(q3,0)=q32(q0,1)=q3，2(q1,1)=q32(q2,1)=q3，2(q3,1)=q32(q0,2)=q3，2(q1,2)=q32(q2,2)=q3，2(q3,2)=q3 12/18/2022143.23.2有穷状态自动机有穷状态自动机 状态说明状态说明状态状态输入字符

11、输入字符012开始状态开始状态q0q1q3q3q1q2q3q3终止状态终止状态q2q1q3q3q3q3q3q3表表3-2 2转换函数转换函数12/18/2022153.23.2有穷状态自动机有穷状态自动机 将将扩充为扩充为对任意的对任意的qQ，w*，a，定义，定义 12/18/2022163.23.2有穷状态自动机有穷状态自动机 两值相同，不用区分这两个符号。两值相同，不用区分这两个符号。12/18/2022173.23.2有穷状态自动机有穷状态自动机 确定的有穷状态自动机确定的有穷状态自动机由于对于任意的由于对于任意的qQ，a，(q，a)均有均有确定的值，所以，将这种确定的值，所以，将这种F

12、A称为称为确定的有穷状确定的有穷状态自动机态自动机(deterministic finite automaton(deterministic finite automaton，DFA)DFA)12/18/2022183.23.2有穷状态自动机有穷状态自动机 M接受接受(识别识别)的语言的语言 对对于于 x*如如果果(q，w)F，则则称称x被被M接接受受，如果如果(q，w)F，则称，则称M不接受不接受x。L(M)=x|x*且且(q，w)F称为由称为由M接受接受(识别识别)的语言的语言 L(M1)=L(M2)=02n|n1 如果如果L(M1)=L(M2)，则称，则称M1与与M2等价。等价。12/1

13、8/2022193.23.2有穷状态自动机有穷状态自动机 例例 3-2 3-2构造一个构造一个DFA，它接受的语言为，它接受的语言为x000y|x，y0，1*q0M的启动状态；的启动状态；q1M读读到到了了一一个个0，这这个个0可可能能是是子子串串“000”的的第第1个个0；q2M在在q1后后紧紧接接着着又又读读到到了了一一个个0，这这个个0可可能能是子串是子串“000”的第的第2个个0；q3M在在q2后后紧紧接接着着又又读读到到了了一一个个0，发发现现输输入入字字符符串串含含有有子子串串“000”；因因此此，这这个个状状态态应应该该是是终终止状态。止状态。12/18/2022203.23.2

14、有穷状态自动机有穷状态自动机 (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；12/18/2022213.23.2有穷状态自动机有穷状态自动机 (q2,1)=q0M在在刚刚刚刚

15、发发现现了了00后后，读读到到了了一一个个1，表表明明在在读读入入这这个个1之之前前所所读读入入的的00并并不不是是子子串串“000”的的前前两两个个0，因因此此，M需需要要重重新新回回到到状状态态q0，以以寻寻找找子子串串“000”的的第第1个个0；(q3,0)=q3M找找到到了了子子串串“000”，只只用用读入该串的剩余部分。读入该串的剩余部分。(q3,1)=q3M找找到到了了子子串串“000”，只只用用读入该串的剩余部分。读入该串的剩余部分。12/18/2022223.23.2有穷状态自动机有穷状态自动机 M=(q0，q1，q2，q3，0，1，(q0,0)=q1，(q1,0)=q2，(q

16、2,0)=q3，(q0,1)=q0，(q1,1)=q0，(q2,1)=q0，(q3,0)=q3，(q3,1)=q3，q0，q3)状态说明状态说明状态状态输入字符输入字符01开始状态开始状态q0q1q0q1q2q0q2q3q0终止状态终止状态q3q3q312/18/2022233.23.2有穷状态自动机有穷状态自动机 一种更为直观的表示一种更为直观的表示12/18/2022243.23.2有穷状态自动机有穷状态自动机 状态转移图状态转移图(transition diagram)(transition diagram)qQq是该有向图中的一个顶点；是该有向图中的一个顶点；(q，a)=p图图中中有有

17、一一条条从从顶顶点点q到到顶顶点点p的标记为的标记为a的弧；的弧；qF标记为标记为q的顶点被用双层圈标出；的顶点被用双层圈标出；用标有用标有S的箭头指出的箭头指出M的开始状态。的开始状态。状态转移图又可以叫做状态转移图又可以叫做状态转换图。状态转换图。12/18/2022253.23.2有穷状态自动机有穷状态自动机 例例 3-3 3-3构造一个构造一个DFA，它接受的语言为，它接受的语言为x000|x0，1*。状态状态q0读到的读到的0可能是输入字符串的最后三个可能是输入字符串的最后三个0的第的第1个个0；在在状状态态q1紧紧接接着着读读到到的的0可可能能是是输输入入字字符符串串的的最最后三个

18、后三个0的第的第2个个0；在在状状态态q2紧紧接接着着读读到到的的0可可能能是是输输入入字字符符串串的的最最后三个后三个0的第的第3个个0；12/18/2022263.23.2有穷状态自动机有穷状态自动机 在在状状态态q3紧紧接接着着读读到到的的0也也可可能能是是输输入入字字符符串串的的最后三个最后三个0的第的第3个个0；如果在状态如果在状态q1，q2，q3读到的是读到的是1，则要重新检，则要重新检查输入串是否以三个查输入串是否以三个0结尾。结尾。12/18/2022273.23.2有穷状态自动机有穷状态自动机 几点值得注意几点值得注意定义定义FA时，常常只给出时，常常只给出FA相应的状态转移

19、相应的状态转移图就可以了。图就可以了。对于对于DFA来说，并行的弧按其上的标记字来说，并行的弧按其上的标记字符的个数计算，对于每个顶点来说，它的符的个数计算，对于每个顶点来说，它的出度恰好等于输入字母表中所含的字符的出度恰好等于输入字母表中所含的字符的个数。个数。12/18/2022283.23.2有穷状态自动机有穷状态自动机 不难看出，字符串不难看出，字符串x被被FAM接受的充分必接受的充分必要条件是，在要条件是，在M的状态转移图中存在一条从的状态转移图中存在一条从开始状态到某一个终止状态的有向路，该开始状态到某一个终止状态的有向路，该有向路上从第有向路上从第1条边到最后一条边的标记依条边到

20、最后一条边的标记依次并置而构成的字符串次并置而构成的字符串x。简称此路的标记。简称此路的标记为为x。一个一个FA可以有多于可以有多于1个的终止状态。个的终止状态。12/18/2022293.23.2有穷状态自动机有穷状态自动机 接受语言接受语言x000|x0，1*x001|x0，1*的的FA 12/18/2022303.23.2有穷状态自动机有穷状态自动机 即时描述即时描述(instantaneous description(instantaneous description，ID ID）x，y*，(q0，x)=q,xqy称为称为M的一个的一个即时即时描述，描述，表示表示xy是是M正在处理的一

21、个字符串，正在处理的一个字符串，x引引导导M从从q0启动并到达状态启动并到达状态q，M当前正注视着当前正注视着y的首字符。的首字符。如如果果xqay是是M的的一一个个即即时时描描述述，且且(q，a)=p，则，则xqayMxapy。12/18/2022313.23.2有穷状态自动机有穷状态自动机 Mn：表示：表示M从即时描述从即时描述经过经过n次移动到次移动到达即时描述达即时描述。M存在即时描述存在即时描述1，2，n-1，使得，使得M1，1M2，n-1M当当n=0n=0时，有时，有=。即。即M M 0 0 。M M +：表表示示M M从从即即时时描描述述经经过过至至少少1 1次次移移动动到到达即

22、时描述达即时描述。M M*：表示：表示M M从即时描述从即时描述经过若干步移动经过若干步移动到达即时描述到达即时描述。12/18/2022323.23.2有穷状态自动机有穷状态自动机 当意义清楚时，我们将符号当意义清楚时，我们将符号M、Mn、M*、M+中的中的M省去，分别用省去，分别用、n、*、+表示。表示。12/18/2022333.23.2有穷状态自动机有穷状态自动机 对下图所示的对下图所示的DFADFA有如下的有如下的IDID转换：转换：12/18/2022343.23.2有穷状态自动机有穷状态自动机 q01010010001 1q0010010001 10q110010001 101q

23、00010001 1010q1010001 10100q210001 101001q00001 1010010q1001 10100100q201 12/18/2022353.23.2有穷状态自动机有穷状态自动机 101001000q31 1010010001q0即 q0101001000110 1010010001q0 q01010010001+1010010001q0 q01010010001*1010010001q0 12/18/2022363.23.2有穷状态自动机有穷状态自动机 对于x*,q0 x1+x1q0 q0 x10+x10q1 q0 x100+x100q2 q0 x000+x

24、000q3 12/18/2022373.23.2有穷状态自动机有穷状态自动机 能引导能引导FA从开始状态到达从开始状态到达q的字符串的集合为：的字符串的集合为：set(q)=x|x*，(q0，x)=q对图对图3-3所给的所给的DFA 中的所有中的所有q q，求，求set(q)set(q)。12/18/202238set(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个集合是两两互

25、不相交。个集合是两两互不相交。12/18/2022393.23.2有穷状态自动机有穷状态自动机 对对于于任任意意一一个个FAM=(Q，q0，F)我我们可以按照如下方式定义关系们可以按照如下方式定义关系RM：对对 x，y*，xRMy qQ，使使 得得xset(q)和和yset(q)同时成立。同时成立。按照这个定义所得到的关系实际上是按照这个定义所得到的关系实际上是*上上的一个等价关系。利用这个关系，可以将的一个等价关系。利用这个关系，可以将*划分成不多于划分成不多于|Q|个等价类。个等价类。12/18/2022403.23.2有穷状态自动机有穷状态自动机 例例 3-4 3-4 构造一个构造一个D

26、FA，它接受的语言，它接受的语言为为0n1m2k|n,m,k1。q0M的启动状态；的启动状态；q1M读读到到至至少少一一个个0，并并等等待待读读更更多多的的0；q2M读读到到至至少少一一个个0后后，读读到到了了至至少少一一个个1，并等待读更多的，并等待读更多的1；q3M读到至少一个读到至少一个0后跟至少一个后跟至少一个1后，后，并且接着读到了至少一个并且接着读到了至少一个2。12/18/2022413.23.2有穷状态自动机有穷状态自动机先设计先设计“主体框主体框架架”再补充细节再补充细节12/18/202242 3.2 3.2有穷状态自动机有穷状态自动机当当FA一旦进入状态一旦进入状态qt，

27、它就无法离开此状，它就无法离开此状态。所以，态。所以，qt相当于一个陷阱状态相当于一个陷阱状态(trap)。一般地，我们将陷阱状态用作在其他状态一般地，我们将陷阱状态用作在其他状态下发现输入串不可能是该下发现输入串不可能是该FA所识别的语言所识别的语言的句子时进入的状态。在此状态下，的句子时进入的状态。在此状态下，FA读读完输入串中剩余的字符。完输入串中剩余的字符。12/18/2022433.23.2有穷状态自动机有穷状态自动机在构造一个识别给定语言的在构造一个识别给定语言的FA时，用画图时，用画图的方式比较方便、直观。我们可以先根据的方式比较方便、直观。我们可以先根据语言的主要特征画出该语言

28、的主要特征画出该FA的的“主体框架主体框架”，然后再去考虑画出一些细节要求的内容。，然后再去考虑画出一些细节要求的内容。12/18/2022443.23.2有穷状态自动机有穷状态自动机FA的状态具有一定的记忆功能：不同的状的状态具有一定的记忆功能：不同的状态对应于不同的情况，由于态对应于不同的情况，由于FA只有有穷个只有有穷个状态，所以，在识别一个语言的过程中，状态，所以，在识别一个语言的过程中，如果有无穷种情况需要记忆，我们肯定是如果有无穷种情况需要记忆，我们肯定是无法构造出相应的无法构造出相应的FA的。的。12/18/2022453.23.2有穷状态自动机有穷状态自动机例例 3-5 3-5

29、构造一个构造一个DFA，它接受的语言，它接受的语言为为x|x0，1*，且当把，且当把x看成二进看成二进制数时，制数时，x模模3与与0同余同余。q0对应除以对应除以3余数为余数为0的的x组成的等价类；组成的等价类；q1对应除以对应除以3余数为余数为1的的x组成的等价类；组成的等价类；q2对应除以对应除以3余数为余数为2的的x组成的等价类；组成的等价类；qsM的开始状态。的开始状态。12/18/2022463.23.2有穷状态自动机有穷状态自动机qs在此状态下读入在此状态下读入0时，有时，有x=0，所以应，所以应该进入状态该进入状态q0；读入；读入1时，有时，有x=1，所以应该，所以应该进入状态进

30、入状态q1。即：。即：(qs，0)=q0；(qs，1)=q1 。12/18/2022473.23.2有穷状态自动机有穷状态自动机q0能能引引导导M到到达达此此状状态态的的x除除以以3余余0，所以有：所以有：x=3*n+0。读读入入0时时，引引导导M到到达达下下一一个个状状态态的的字字符符串串为为x0，x0=2*(3*n+0)=3*2*n+0。所所以以，(q0，0)=q0；读入读入1时，时，M到达下一个状态的字符串为到达下一个状态的字符串为x1，x1=2*(3*n+0)+1=3*2*n+1。所以，。所以，(q0，1)=q1；12/18/2022483.23.2有穷状态自动机有穷状态自动机q1能能

31、引引导导M到到达达此此状状态态的的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)=q0 12/18/2022493.23.2有穷状态自动机有穷状态自动机q2能能引引导导M到到达达此此状状态态的的x除除以以3余余2，所所以以：x=3*n+2。读读入入0时时，引引导导M

32、到到达达下下一一个个状状态态的的字字符符串串为为x0，x0=2*(3*n+2)=3*2*n+4=3*(2*n+1)+1。所所以以(q2，0)=q1；读入读入1时，引导时，引导M到达下一个状态的字符串为到达下一个状态的字符串为x1，x1=2*(3*n+2)+1=3*2*n+4+1=3*(2*n+1)+2。所以，。所以，(q2，1)=q2 。12/18/2022503.23.2有穷状态自动机有穷状态自动机接受语言接受语言x|x0，1*，且当把，且当把x看成二进看成二进制数时，制数时，x模模3与与0同余同余的的DFA如下：如下：12/18/2022513.23.2有穷状态自动机有穷状态自动机例例 3

33、-6 3-6构造一个构造一个DFA，它接受的语言，它接受的语言L=x|x0，1*，且对，且对x中任意一个长度不大中任意一个长度不大于于5的子串的子串a1a2an，a1+a2+an3，n5 。输入串为输入串为 a1a2aiai+4ai+5am12/18/2022523.23.2有穷状态自动机有穷状态自动机当当i=1，2，3，也就是，也就是M读到输入串的第读到输入串的第1、2、3个字符时，它需要将这些字符记下来。个字符时，它需要将这些字符记下来。因为因为a1ai可能需要用来判定输入串的最可能需要用来判定输入串的最初初45个字符组成的子串是否满足语言的要个字符组成的子串是否满足语言的要求。求。当当i

34、=4，5，也就是，也就是M读到输入串的第读到输入串的第4、5个个字符时，在字符时，在a1+a2+ai3的情况下，的情况下，M需要将需要将a1ai记下来；在记下来；在a1+a2+ai3时，时，M应该进入陷阱状态应该进入陷阱状态qt。12/18/2022533.23.2有穷状态自动机有穷状态自动机当当i=6，也就是，也就是M读到输入串的第读到输入串的第6个字符，个字符，此时，以前读到的第此时，以前读到的第1个字符个字符a1就没有用了，就没有用了，此时它要看此时它要看a2+a3+a63是否成立，如果是否成立，如果成立，成立，M需要将需要将a2a6记下来；在记下来；在a2+a3+ai3时，时，M应该进

35、入陷阱状态应该进入陷阱状态qt。12/18/2022543.23.2有穷状态自动机有穷状态自动机当当M完成对子串完成对子串a1a2aiai+4的考察，并发的考察，并发现它满足语言的要求时，现它满足语言的要求时，M记下来的是记下来的是aiai+4，此时它读入输入串的第，此时它读入输入串的第i+5个字符个字符ai+5，以前读到的第，以前读到的第i个字符个字符ai就没有用了，就没有用了，此时它要看此时它要看ai+1+ai+2+ai+53是否成立，是否成立，如果成立，如果成立，M需要将需要将ai+1，ai+2，ai+5记下记下来；在来；在ai+1+ai+2+ai+53时，时，M应该进入陷应该进入陷阱状

36、态阱状态qt。12/18/2022553.23.2有穷状态自动机有穷状态自动机M需要记忆的内容有：需要记忆的内容有：什么都未读入什么都未读入20=1种；种；记录有记录有1个字符个字符21=2种；种；记录有记录有2个字符个字符22=4种；种；记录有记录有3个字符个字符23=8种；种；记录有记录有4个字符个字符24-1=15种；种；记录有记录有5个字符个字符25-6=26种；种；记录当前的输入串不是句子记录当前的输入串不是句子1种。种。12/18/2022563.23.2有穷状态自动机有穷状态自动机状态设置状态设置qM还未读入任何字符；还未读入任何字符；qt陷阱状态；陷阱状态；qa1a2aiM记记

37、录录有有i个个字字符符，1i5。a1，a2，ai0，1。取取DFAM=(Q，0，1，q，F)F=qqa1a2ai|a1，a2，ai0，1且且1i5且且a1+a2+ai3Q=qtF 12/18/2022573.23.2有穷状态自动机有穷状态自动机(q，a1)=qa1(qa1，a2)=qa1a2(qa1a2，a3)=qa1a2a3 qa1a2a3a如果a1+a2+a3+a3(qa1a2a3，a)=qt如果a1+a2+a3+a3 12/18/2022583.23.2有穷状态自动机有穷状态自动机 qa1a2a3a4a 如果a1+a2+a3+a4+a3(qa1a2a3a4，a)=qt如果a1+a2+a3

38、+a4+a3qa2a3a4a5a a2+a3+a4+a5+a3(qa1a2a3a4a5，a)=qt如果a2+a3+a4+a5+a3(qt，a1)=qt12/18/2022593.3 NFA 3.3 NFA 3.3.1 3.3.1 作为对作为对DFADFA的修改的修改 希望是接受希望是接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA如下：如下：12/18/2022603.3.1 3.3.1 作为对作为对DFADFA的修改的修改希望是接受希望是接受x|x0，1*，且，且x的倒数第的倒数第10个字符为个字符为1的的FA如下如下 ：12/18/2022613.3.1 3.3.1 作为对

39、作为对DFADFA的修改的修改这这两两个个图图所所给给的的“FA”与与前前面面我我们们所所定定义义的的FA，即，即DFA，的区别在于：，的区别在于：并并不不是是对对于于所所有有的的(q，a)Q,(q，a)都有一个状态与它对应；都有一个状态与它对应；并不是对于所有的并不是对于所有的(q，a)Q,(q，a)只对应一个状态。只对应一个状态。“FA”在任意时刻可以处于有穷多个状态。在任意时刻可以处于有穷多个状态。“FA”具有具有“智能智能”。12/18/2022623.3.2 NFA3.3.2 NFA的形式定义的形式定义 不不确确定定的的有有穷穷状状态态自自动动机机(non-deterministic

40、finiteautomaton,NFA)M是一个五元组是一个五元组M=(Q，q0，F)Q、q0、F的意义同的意义同DFA。：Q2Q，对对(q，a)Q，(q，a)=p1，p2，pm表表示示M在在状状态态q读读入入字字符符a，可可以以选选择择地地将将状状态态变变成成p1、或或者者p2、或或者者pm，并并将将读读头头向向右右移移动动一一个个带带方方格格而而指指向向输输入入字字符符串的下一个字符。串的下一个字符。12/18/2022633.3.2 NFA3.3.2 NFA的形式定义的形式定义 FA的状态转移图、的状态转移图、FA的状态对应的等价类、的状态对应的等价类、FA的即时描述对的即时描述对NFA

41、都有效。都有效。接受接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA对应的移动函数定义表。对应的移动函数定义表。12/18/2022643.3.2 NFA3.3.2 NFA的形式定义的形式定义 状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0，q1q0，q2q1q3q2q3终止状态终止状态q3q3q312/18/2022653.3.2 NFA3.3.2 NFA的形式定义的形式定义 接受接受x|x0，1*，且，且x的倒数第的倒数第10个字符个字符为为1的的FA对应的移动函数定义表。对应的移动函数定义表。12/18/2022663.3.2 NFA3.3.2 NF

42、A的形式定义的形式定义 状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0q0，q1q1q2q2q2q3q3q3q4q4q4q5q5q5q6q6q6q7q7q7q8q8q8q9q9q9q10q10终止状态终止状态q1012/18/2022673.3.2 NFA3.3.2 NFA的形式定义的形式定义将将扩充为扩充为对任意的对任意的qQ，w*，a，定义，定义 12/18/2022683.3.2 NFA3.3.2 NFA的形式定义的形式定义和关于和关于DFADFA的结论一样，两值相同，也不的结论一样，两值相同，也不用区分这两个符号。用区分这两个符号。12/18/2022693.3.

43、2 NFA3.3.2 NFA的形式定义的形式定义 进一步扩充进一步扩充的定义域：的定义域：2Q*2Q。对任意的对任意的P Q，w*12/18/2022703.3.2 NFA3.3.2 NFA的形式定义的形式定义 由于，对由于，对(q，w)Q*所以，不一定严格地区分所以，不一定严格地区分的第的第1个分量是一个个分量是一个状态还是一个含有一个元素的集合。状态还是一个含有一个元素的集合。12/18/2022713.3.2 NFA3.3.2 NFA的形式定义的形式定义 对任意的对任意的qQ，w*，a：(q，wa)=(q，w)，a)对输入字符串对输入字符串a1a2an (q，a1a2an)=(q,a1)

44、,a2)，)，an)。12/18/2022723.3.2 NFA3.3.2 NFA的形式定义的形式定义M接受接受(识别识别)的语言的语言 对对于于 x*，如如果果(q0，w)F，则则称称x被被M接接受受，如如果果(q0，w)F=，则称则称M不接受不接受x。L(M)=x|x*且且(q0，w)F，称称为由为由M接受接受(识别识别)的语言。的语言。12/18/2022733.3.3 NFA3.3.3 NFA与与DFADFA等价等价 对于一个输入字符，对于一个输入字符，NFA与与DFA的差异是前的差异是前者可以进入若干个状态，而后者只能进入者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从一个

45、惟一的状态。虽然从DFA看待问题的看待问题的角度来说，角度来说，NFA在某一时刻同时进入若干在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的个状态，但是，这若干个状态合在一起的“总效果总效果”相当于它处于这些状态对应的相当于它处于这些状态对应的一个一个“综合状态综合状态”。因此，我们考虑让。因此，我们考虑让DFA用一个状态去对应用一个状态去对应NFA的一组状态。的一组状态。12/18/2022743.3.3 NFA3.3.3 NFA与与DFADFA等价等价 NFAM1=(Q，1，q0，F1)与与DFAM2=(Q2，2，q0，F2)的对应关系：的对应关系：NFA从开始状态从开始状态q0

46、启动，我们就让相应的启动，我们就让相应的DFA从状态从状态q0启动。所以启动。所以q0=q0。对于对于NFA的一个状态组的一个状态组q1，q2，qn，如，如果果NFA在此状态组时读入字符在此状态组时读入字符a后可以进入状态后可以进入状态组组p1，p2，pm,则让相应的则让相应的DFA在状态在状态q1，q2，qn读入字符读入字符a时，进入状态时，进入状态p1，p2，pm。12/18/2022753.3.3 NFA3.3.3 NFA与与DFADFA等价等价 定理定理 3-1 3-1NFA与与DFA等价。等价。证明：证明：(1)(1)构造与构造与M1等价的等价的DFAM2。M1=(Q，1，q0，F1

47、)M2=(Q2，2，q0，F2)Q2=2Q F2=p1，p2，pm|p1，p2，pm Q&p1，p2，pmF1 12/18/2022763.3.3 NFA3.3.3 NFA与与DFADFA等价等价 2(q1，q2，qn，a)=p1，p2，pm1(q1，q2，qn，a)=p1，p2，pm (2)证明证明1(q0，x)=p1，p2，pm2(q0，x)=p1，p2，pm。设设x*，施归纳于，施归纳于|x|x=，1(q0，)=q0,2(q0，)=q0 12/18/2022773.3.3 NFA3.3.3 NFA与与DFADFA等价等价 设当设当|x|=n是结论成立。下面证明当是结论成立。下面证明当|x

48、|=n+1是结是结论也成立。不妨设论也成立。不妨设x=wa，|w|=n，a1 1(q(q0 0，wa)=wa)=1 1(1 1(q(q0 0，w)w)，a)a)=1 1(q(q1 1，q q2 2，q qn n，a)a)=p =p1 1，p p2 2，p pm m 由归纳假设，由归纳假设，1 1(q(q0 0，w)=qw)=q1 1，q q2 2，q qn n 2 2(q(q0 0，w)=w)=qq1 1，q q2 2，q qn n 12/18/2022783.3.3 NFA3.3.3 NFA与与DFADFA等价等价 根据根据2的定义，的定义，2(q1，q2，qn，a)=p1，p2，pm1(q

49、1，q2，qn，a)=p1，p2，pm 所以，所以，2(q0，wa)=2(2(q0，w)，a)=2(q1，q2，qn，a)=p1，p2，pm 12/18/2022793.3.3 NFA3.3.3 NFA与与DFADFA等价等价 故故，如如果果1(q0，wa)=p1，p2，pm则则必必有有2(q0，wa)=p1，p2，pm。由由上上述述推推导导可可知知，反反向向的的推推导导也也成成立立。这这就就是说，结论对是说，结论对|x|=n+1也成立。也成立。由归纳法原理，结论对由归纳法原理，结论对 x*成立。成立。12/18/2022803.3.3 NFA3.3.3 NFA与与DFADFA等价等价(3)证

50、明证明L(M1)=L(M2)设设xL(M1)，且且1(q0，x)=p1，p2，pm，从而从而1(q0，x)F1,这就是说，这就是说，p1，p2，pmF1，由由F2的定义，的定义，p1，p2，pmF2。12/18/2022813.3.3 NFA3.3.3 NFA与与DFADFA等价等价再由再由(2)知，知，2(q0，x)=p1，p2，pm所以，所以，xL(M2)。故。故L(M1)L(M2)。反过来推，可得反过来推，可得L(M2)L(M1)。从而从而L(M1)=L(M2)得证。得证。综上所述，定理成立。综上所述，定理成立。12/18/202282例例 3-7 3-7 图图3-93-9所示的所示的N