有限自动机理论3章有限状态自动机.ppt

《有限自动机理论3章有限状态自动机.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论3章有限状态自动机.ppt（373页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章有限状态自动机有限状态自动机定义语言定义语言可以从两个方面可以从两个方面进行进行：）从）从产生产生语言的角度；语言的角度；）从）从接收接收(或识别或识别)语言的角度。语言的角度。形式语言研究内容形式语言研究内容产生产生一个语言一个语言:1)定义语言中的定义语言中的基本句子基本句子;2)根据根据其余句子其余句子的的形成规则形成规则，产生产生出该语言所包含的所有出该语言所包含的所有句子句子。有限自动机有限自动机研究内容研究内容使用某种使用某种自动机模型自动机模型来接收字符串来接收字符串接收接收的所有字符串形成的集合，也的所有字符串形成的集合，也是一个语言是一个语言统一的理论形式语言与自

2、动机作为统一的理论形式语言与自动机作为统一的理论,实实际上包括际上包括3个方面的内容个方面的内容:1)形式语言形式语言理论理论(文法产生语言文法产生语言)2)自动机自动机理论理论(自动机接收语言自动机接收语言)3)形式语言与自动机的形式语言与自动机的等价性等价性理论理论(文文法与自动机等价转换法与自动机等价转换)有限状态自动机有限状态自动机FA(FinitestateAutomaton)FA是为研究是为研究有限存储有限存储的计算过程的计算过程正则语言正则语言而抽象出的一种计算模型。而抽象出的一种计算模型。两类有限状态自动机有限状态自动机接收器接收器判断是否判断是否接收接收输入串；输入串；转换器

3、转换器对给定输入串对给定输入串产生输出产生输出。FA还可以分为还可以分为确定的确定的FA-DFA DeterministicFinitestateAutomaton非确定非确定FA-NFANon-deterministicFinitestateAutomaton等价性等价性有限状态自动机有限状态自动机接收接收的语言称的语言称为为有限状态语言有限状态语言-FSL从从产生产生语言角度而言，语言角度而言，FSL就就是是右线性语言右线性语言-RLL从从(正则正则)运算运算角度而言，角度而言，FSL就是就是正则语言正则语言-RL有限状态自动机除在理论上的研有限状态自动机除在理论上的研究价值外究价值外还在

4、还在数字电路设计数字电路设计、编译技术、编译技术(词词法分析法分析)、系统辅助软件、系统辅助软件(文本编辑文本编辑程序程序)、漏洞检测漏洞检测、交通控制交通控制等应用等应用领域得到广泛应用领域得到广泛应用3.1有限状态自动机有限状态自动机有限状态自动机是具有有限状态自动机是具有离散离散输入和输入和离散离散输出的一种输出的一种数学模型数学模型。l有限状态自动机是否有限状态自动机是否接收串接收串wl有限状态自动机是否有限状态自动机是否接收语言接收语言L有限状态自动机有限状态自动机物理模型物理模型a1a2a3 aj anan+1FSC一个输入一个输入存储带（输入带）存储带（输入带），带，带被分解为被

5、分解为单元单元，每个单元存放一个，每个单元存放一个输入符号输入符号(字母表上的符号字母表上的符号)。整个输入串从带的左端点开始存整个输入串从带的左端点开始存放，而带的右端可以放，而带的右端可以无限扩充无限扩充；一个有穷状态控制器（一个有穷状态控制器（FSC）该控制器的状态只能是有限多个该控制器的状态只能是有限多个FSC通过通过读头读头读取读取当前带上单元当前带上单元的字符。的字符。初始时，读头对应带的初始时，读头对应带的最左单最左单元元，每读取一个字符，读头，每读取一个字符，读头向右向右自动移动一个单元。自动移动一个单元。读头读头不不允许允许向左移动向左移动。有限状态自动机的一个动作为：有限状

6、态自动机的一个动作为：读头读取带上当前单元的字符读头读取带上当前单元的字符FSC根据当前根据当前FSC的的状态状态和读取和读取的的字符字符，进行进行状态改变状态改变；将读头将读头向右移动向右移动一个单元。一个单元。有限态自动机的动作有限态自动机的动作简化简化为：为：FSC根据根据当前状态当前状态和和当前读取的带上当前读取的带上字符字符进行进行状态改变状态改变。定义定义3-1有限状态自动机有限状态自动机FAFA是一个五元式是一个五元式FA=(Q，q0，F)Q是有限状态的集合是有限状态的集合是字母表，即输入带上的字是字母表，即输入带上的字符集合符集合q0Q是开始状态是开始状态F Q是接收状态是接收

7、状态(终终止状止状态态)集合集合是是QQ的状态转换函数的状态转换函数即即(q，x)=q代表自动机在状态代表自动机在状态q时，扫描字符时，扫描字符x后到达状态后到达状态q有限状态自动机的状态转换函有限状态自动机的状态转换函数的个数应该为数的个数应该为|Q|*|对于对于Q中的每个中的每个状态状态，需要定，需要定义对应义对应每个每个字母字母的的状态转换状态转换。DFA这种有限状态自动机为这种有限状态自动机为确定的有确定的有限状态自动机限状态自动机DFA。例3-1定义定义DFA为：为：DFA=(q0,q1,0,1,q0,q0)其中其中：的表示的表示：函数形式函数形式(q0，0)=q1(q0，1)=q1

8、(q1，0)=q1(q1，1)=q0的表示的表示：状态矩阵：状态矩阵Q0q01q1q1q1q1q0的表示的表示:状态图形式状态图形式状态图是一个状态图是一个有向有向、有、有循环循环的图的图一个节点表示一个状态；一个节点表示一个状态；若有若有(q，x)=q，则，则状态状态q到状态到状态q有一条有一条有向边有向边，并，并用字母用字母x作标记。作标记。的表示 指向的状态是开始状态指向的状态是开始状态 两个圆圈两个圆圈代表代表接收状态接收状态；的表示：状态图状态图q11010q0 用状态图表示一个用状态图表示一个DFADFA 有向边的有向边的数目数目就是状态转换函数就是状态转换函数的个数。的个数。默认

9、默认(q q,)=)=q q不是状态转换函数不是状态转换函数3.2 3.2 有限状态自动机接收语言有限状态自动机接收语言对于对于DFADFA，给定串，给定串w=xw=x1 1x x2 2x xn n 初始时，初始时，DFADFA处于开始状态处于开始状态q q0 0 从左到右逐个字符地扫描串从左到右逐个字符地扫描串w w 在在(q(q0 0，x x1 1)=q)=q1 1的作用下的作用下 DFADFA处于状态处于状态q q1 1 在在(q(q1 1，x x2 2)=q)=q2 2的的作用下的的作用下 DFADFA处于状态处于状态q q2 2 当将串当将串w w扫描结束扫描结束后，后，若若DFAD

10、FA处于某一个处于某一个接收状态接收状态，则有限状态自动机能够则有限状态自动机能够接收接收串串w w对于对于可接收串可接收串DFADFA从从开开始始状状态态开开始始，在在扫扫描描串串的的过程中，过程中，状态逐个地变化状态逐个地变化,串扫描结束后，串扫描结束后，到达到达某个某个接收状态接收状态。对于对于不可接收串不可接收串DFADFA从从开开始始状状态态开开始始，在在扫扫描描串串的的过程中，过程中，状态逐个地变化状态逐个地变化,串扫描结束后，串扫描结束后，处于处于非接收状态非接收状态。对于字母表对于字母表上的上的DFADFA 能够接收的所有串的集合，就是能够接收的所有串的集合，就是DFADFA能

11、接收的语言，记为能接收的语言，记为L(DFA)L(DFA)也称为有限状态语言（也称为有限状态语言（FSLFSL）思考思考如何如何形式化形式化定义定义L(DFA)L(DFA)?定义3-4 扩展的状态转换函数扩展的状态转换函数给定给定DFADFA，扩展的状态转换函数，扩展的状态转换函数 *：Q Q*QQ 即即 *(q,q,w w)=q)=q即即DFADFA在在一一个个状状态态q q时时，扫扫描描串串w w后后到达唯一到达唯一确定确定的状态的状态qq递归扩展的状态转换函数 *(q q,)=)=q q *(q,q,a a)=)=(q,a(q,a)其中其中a a对于串对于串w=w=a a（+）*（q q

12、，w w）=*(q(q，a a）=(*(q,q,),),a a)或者或者 对于串对于串w=w=a a *(q(q，w w)=*(q(q，a a)=*(q(q，a a),),)定义定义3-6 DFA3-6 DFA接收的语言接收的语言DFA=(Q,qDFA=(Q,q0 0，F)F)接收的语言接收的语言 L(DFA)=L(DFA)=w|w|*(q(q0 0,w),w)FF思考思考如何描述如何描述在某个在某个时刻时刻，DFA所处的情况？所处的情况？定义定义3-7 DFA3-7 DFA的瞬时描述（格局）的瞬时描述（格局）格局是一个二元式：格局是一个二元式：q qy y q q是是DFADFA当前状态当前

13、状态 y y是输入带上还没有被扫描到的串是输入带上还没有被扫描到的串 读头将扫描读头将扫描y y串的第串的第1 1个字母个字母 在在扫扫描描串串的的过过程程中中，格格局局在在发发生转换生转换(改变改变)格格局局的的(一一次次)转转换换的的原原因因是是由由于于函数函数的的(一次一次)作用作用 如果当前格局为：如果当前格局为：q qa ar r 有有函数：函数：(q(q，a)=qa)=q 则下一格局为：则下一格局为：qrqr 格局的转换可以记为：格局的转换可以记为：qarqar =qrqrDFA的特殊格局初始格局为：初始格局为：q q0 0w w接收格局为：接收格局为：q qf f其中，其中，q

14、qf f是某个接收状态是某个接收状态 使用使用=*代表格局的代表格局的任意次任意次转换转换使用使用=+代表格局的代表格局的多次多次转换转换可以使用可以使用格局的转换格局的转换方式定义方式定义FSLFSLDFADFA接收的语言接收的语言 L(DFA)=L(DFA)=w|q w|q0 0w=w=*q qf f；ww*且且q qf fFF 定义3-8 DFA停机DFA将输入串扫描结束时将输入串扫描结束时(自动自动)停机停机这是这是DFA唯一的停机情况唯一的停机情况注意1：DFA将输入串扫描结束停机时，将输入串扫描结束停机时，如果如果DFA处于某一个处于某一个接收状态接收状态，则表示接收整个输入串；则

15、表示接收整个输入串；反之，则表示反之，则表示不接收不接收整个输入串整个输入串;注意2：对于状态对于状态q,如果如果不能接收不能接收字母字母a则将状态转换到一个特殊的状态：则将状态转换到一个特殊的状态：陷阱状态陷阱状态qt陷阱陷阱状态状态qt不能够改变为其他状态不能够改变为其他状态即即对于对于a(qt，a)=qtqt不能够不能够接收接收任意字母任意字母构造构造DFA，分别接收语言，分别接收语言、0、01、0*、0+(0+1)*、(0+1)+01*0、1*00(0+1)*(0+1)*00(0+1)*0(0+1)*10(0+1)*0+1(0+1)*1定理3-1 每个每个FSLFSL都是一个都是一个右

16、线性语言右线性语言分析：分析：已知已知接收接收FSL的的DFA需要需要构造构造RLG，使得使得L(RLG)=FSL等价等价思路思路DFA最重要的部分是状态转换函数最重要的部分是状态转换函数文法最重要的部分是产生式文法最重要的部分是产生式考虑状态转换函数和产生式的考虑状态转换函数和产生式的等等价作用价作用:将将状态转换函数状态转换函数改造改造为产生式为产生式等价等价思路思路状态转换函数和产生式的状态转换函数和产生式的等价等价作用作用(q,a)=qAaB接收接收a产生产生a状态状态变化变化非终结符号非终结符号变化变化结论结论:DFA:DFA状态状态等价于文法等价于文法非终结符非终结符状态转换函数等

17、价于产生式状态转换函数等价于产生式构造文法的基本思路：构造文法的基本思路：l将将的的DFA的的状态状态当作是当作是RLG的的非终结非终结符符(开始状态就是开始符号开始状态就是开始符号)l对于某个句子：对于某个句子：DFA通过状态的改变，逐步通过状态的改变，逐步（自左向（自左向右）右）接收接收句子的每个字母；句子的每个字母；RLG通过非终结符号的改变，逐步通过非终结符号的改变，逐步（自左向右）（自左向右）产生产生句子的每个字母。句子的每个字母。思考思考DFA的接收状态的作用的接收状态的作用证明假设假设L L是字母表是字母表上的上的FSLFSL，则，则 L=L(DFA)L=L(DFA)DFA=DF

18、A=（Q Q，q q0 0，F F）构造构造右线性右线性文法文法G=(,G=(,Q,Q,q q0 0，P P）其中其中P P为：为：qaqqaq|(q|(q，a)=qa)=q U U qaqa|(q(q，a)Fa)F 特别，若特别，若q q0 0是接收状态，则是接收状态，则 q q0 0对于句子w=x1x2xnDFA：则文法有则文法有(q0,x1)=q1q0 x1q1(q1,x2)=q2q1x2q2(qn-2,xn-1)=qn-1qn-2xn-1qn-1(qn-1,xn)=qn qn-1xnqn或或qn-1xn所以DFA文法文法*(q，)=qq=*q*(q0，w)Fq0=*w注意：注意：陷进状

19、态在文法中是无用非终结符陷进状态在文法中是无用非终结符例例3-2DFA与文法的转换与文法的转换FSLFSL=(0,1)1=(0,1)1*00*接收该语言的接收该语言的DFADFA为：为：q11001q0构造构造正则正则文法产生该语言：文法产生该语言：q00q1|1q1|q10q0|1q1|0定理定理3-2FSL对对补补运算封闭运算封闭证明：设设L L1 1是是上的上的FSL,FSL,且且L L1 1=L(DFA=L(DFA1 1)，DFA DFA1 1=（Q Q，q q0 0，F F）构造构造 DFA DFA2 2=（Q Q，q q0 0，Q Q）DFADFA2 2接收的语言是接收的语言是 L

20、 L1 1的对应的全集的对应的全集,即即*构造构造 DFA DFA3 3=(Q=(Q，q q0 0，Q-FQ-F)L L3 3=L(DFA=L(DFA3 3)L L3 3接收的语言是接收的语言是L L1 1(关于关于*)的的补补 L L3 3也是也是FSLFSL语言。语言。注意此时的此时的DFADFA1 1的的函数的个数为函数的个数为|Q|Q|*|基本的等价替换基本的等价替换l对于状态转换图，有基本的等价替换对于状态转换图，有基本的等价替换l变换为00,113.3 DFA3.3 DFA接收语言的例子接收语言的例子构造构造DFA，接收语言接收语言L=ab基本结构（接收基本句子）基本结构（接收基本

21、句子）q1abq0q2增加增加陷阱状态陷阱状态后的后的DFADFAq1abq0qtbaa,ba,bq2思考思考1 1 如如果果将将该该DFADFA的的所所有有状状态态都都设设置置为为接收状态接收状态(包括陷阱状态包括陷阱状态)，接收的语言是接收的语言是？思考思考2 2 如如果果将将该该自自动动机机的的接接收收状状态态和和非非接收接收状态对调状态对调 接收的语言是接收的语言是？例3-4构造DFA接收语言接收语言L=L=x000yx000y|x,y0,1|x,y0,1*分析 该语言的特点是该语言的特点是 语语言言中中的的每每个个串串都都包包含含连连续续的的3 3个个0 0（即每个串都包含子串（即每

22、个串都包含子串000000）因因此此，对对于于任任何何输输入入串串，有有限限状状态态自自动动机机的的任任务务就就是是要要检检查查该该输输入入串中是否存在子串串中是否存在子串000000，一一旦旦发发现现输输入入串串包包含含有有000000，则则表示表示整个输入串整个输入串是是句子句子。因此，在确认输入串包含因此，在确认输入串包含000000后，后，就就可可以以逐逐一一地地读读入入000000后后面面的的全全部字符，并接收该输入串。部字符，并接收该输入串。思考思考问题的关键是问题的关键是？如何如何发现发现子串子串000000。由由于于字字符符是是逐逐一一读读入入的的，当当从从输输入入串中读入一个

23、串中读入一个0 0时，时，它它有可能有可能是是000000的的第第1 1个个0 0，需要需要记住记住已经出现过一个已经出现过一个0 0；如果紧接着读入的是字符如果紧接着读入的是字符1 1，则刚读入的则刚读入的0 0就不是就不是000000的第的第1 1个个0 0需要需要重新寻找重新寻找000000子串的第子串的第1 1个个0 0；如如果果紧紧接接着着读读入入的的还还是是0 0，它它有有可可能能是是000000的的第第2 2个个0 0，也需要也需要记住记住这个这个0 0，继续读入字符，若是继续读入字符，若是0 0，则，则发现发现000000否则，需要否则，需要重新重新寻找寻找000000。初始状

24、态：初始状态：q q0 0接收接收0 0，到达状态，到达状态q q1 1接收接收00,00,到达状态到达状态q q2 2接收接收000,000,到达状态到达状态q q3 3因此，因此，基本的基本的状态转移函数为：状态转移函数为：(q(q0 0，0)=q0)=q1 1 (q (q1 1，0)=q0)=q2 2 (q (q2 2，0)=q0)=q3 3用于接收基本句子用于接收基本句子000000接收接收000000的状态图的状态图q0000q1q2q3其他状态转移函数为：其他状态转移函数为：(q(q0 0，1)=q1)=q0 0 期待期待0 0的出现的出现 (q(q1 1，1)=q1)=q0 0

25、重新寻找重新寻找000000 (q(q2 2，1)=q1)=q0 0 重新寻找重新寻找000000 (q (q3 3，0)=q0)=q3 3 扫描后续字符扫描后续字符 (q (q3 3，1)=q1)=q3 3 扫描后续字符扫描后续字符状态转移图状态转移图q00111000,1q1q2q3思考思考如果需要接收语言如果需要接收语言L 如何修改有限状态自动机如何修改有限状态自动机?思路：思路：考虑考虑开始状态开始状态的作用的作用思考思考:如果如果DFA的的开始状态开始状态只负责接收输入只负责接收输入串的第一个字母；串的第一个字母；文法的文法的开始符号开始符号只负责串的推导只负责串的推导的开始；的开始

26、；优点是？优点是？状态图为状态图为10qs01000,1q1q2q3q011例3-5构造DFA 接收语言接收语言 L=L=x x001001y y|x|x，y0y0，11*分析：对于任何输入串，对于任何输入串，DFADFA的任务就的任务就是要检查该输入串中是否存在是要检查该输入串中是否存在001001初始状态：初始状态：q q0 0q q1 1 已接收已接收0 0q q2 2 已接收已接收00 00 q q3 3 已接收已接收001 001 q2q1q0状态转移图状态转移图01q31010,10例3-6 构造DFA接收语言接收语言L=L=x x000000|x0|x0，11*q2q3q1q00

27、1110001例3-7构造DFA接收语言接收语言L=L=x x000000 x x001001其中，其中，x0 x0，11*q2q1q001q310001q4101例3-8构造DFA接收语言接收语言L=L=0 02k+3m2k+3m|m,k=0|m,k=0实际上：实际上：2k+3m2k+3m可以表示任意的可以表示任意的非负整数非负整数(除除1 1外外)该语言为该语言为0*-0 状态转移图状态转移图000q1q2q0思考：构造DFA接收语言接收语言L=0L=02k+3m2k+3m|m,k0m,k0 例3-9构造DFA 接收接收00，11上的语言，该语言的上的语言，该语言的 每个句子以每个句子以0

28、 0开头，以开头，以1 1结尾。结尾。状态转移图状态转移图010q1q210qt0,11q0例3-10 构造DFA接收接收00，11上的语言，该语言的每上的语言，该语言的每个字符串个字符串 不包含不包含0000子串子串(语言允许语言允许)000,1qtq1q0q21011或或000,1qtq1q011构造DFA接收接收00，11上的语言，上的语言，该语言的每个字符串不包含该语言的每个字符串不包含0000（语言不允许语言不允许 ）例3-11构造DFA接收接收00，1 1，22上的语言，上的语言，该语言的每个字符串代表的数字该语言的每个字符串代表的数字能整除能整除3 3。分析 如如果果一一个个十十

29、进进制制整整数数的的所所有有位位的的数字的和数字的和能够整除能够整除3 3，那么，那么，这个十进制整数就能够整除这个十进制整数就能够整除3 3；一一个个十十进进制制整整数数除除以以3 3，余余数数只只能能是是1 1、2 2和和0 0；将将整整数数当当作作一一个个字字符符串串，从从左左到到右逐一地读入；右逐一地读入；使使用用3 3个个状状态态分分别别代代表表已已读读入入的的数字的数字的和和除以除以3 3的的余数情况余数情况：(即读入的整数对即读入的整数对3 3的余数情况）的余数情况）q q0 0：已已读入的整数除以读入的整数除以3 3，余数为余数为0 0q q1 1：已已读入的整数除以读入的整数

30、除以3 3，余数为余数为1 1q q2 2：已已读入的整数除以读入的整数除以3 3，余数为余数为2 2思考思考已知已知qi(i=0,1,2)，k=0,1,2应该如何确定应该如何确定j？qiqjk 扫描子串扫描子串w w后后,处于某个状态处于某个状态q qi i，读入当前数字读入当前数字,状态转换情况为状态转换情况为q0l在在此此状状态态读读入入0 0，引引导导DFADFA到到达达下下一状态的输入串为一状态的输入串为w0w0,lw0w0的的各各位位数数字字和和除除以以3 3，余余数数为为0 0。所所以以，DFADFA在在q q0 0状状态态读读入入0 0，应应该该继续保持继续保持q q0 0状态

31、；状态；q0l在在此此状状态态读读入入1 1，引引导导DFADFA到到达达下下一一状状态态的的输输入入串串为为w1w1，w1w1的的各各位位数字和除以数字和除以3 3，余数为余数为1 1。l所所以以，DFADFA在在q q0 0状状态态读读入入1 1，应应该该到达到达q q1 1状态；状态；q0l在此状态读入在此状态读入2 2，引导，引导DFADFA到达下到达下一状态的输入串为一状态的输入串为w2w2，w2w2的各位的各位数字和除以数字和除以3 3，余数为余数为2 2。l所以，所以，DFADFA在在q q0 0状态读入状态读入2 2，应该，应该到达到达q q2 2状态；状态；l存在的问题接收的

32、串包括以接收的串包括以0开始开始的数字串；的数字串；还能够接收还能够接收空串空串思考如何进行改进，使得如何进行改进，使得接收的串不能以接收的串不能以0开始，开始，不能接收不能接收空串空串。定义3-9 set集合对于状态对于状态q，能将，能将DFA从从q0转换到转换到q状态的所有字符串的集合为：状态的所有字符串的集合为：set(qset(q)=w|ww|w*,*(q(q0 0,w)=q,w)=q 则则有限状态自动机有限状态自动机DFADFA接收的接收的语言语言可以定义为：可以定义为：L(DFA)=set(q)其中：其中：q qFF按状态进行划分按状态进行划分对于对于DFADFA，可以定义关系可以

33、定义关系R R 若若 x,yx,y*，qQqQ 则则 xRyxRy 当且仅当当且仅当 xset(q),yset(qxset(q),yset(q)即即R=(x,y)|xset(q),yset(qxset(q),yset(q)；qQqQ 是*上的二元关系上的二元关系 该该关关系系是是集集合合*上上的的一一个个等等价价关关系系，利用该关系，利用该关系，可可以以将将*划划分分为为不不多多于于|Q|Q|个个的的等价类等价类。DFADFA可可以以按按照照语语言言的的特特点点给给出出字字母母表表*的的一一个个划划分分，这这种种划划分分相相当当于于*上的一个等价分类。上的一个等价分类。DFA DFA每个每个状

34、态状态对应着一个对应着一个等价类等价类 利用一个利用一个状态状态去表示一个去表示一个等价等价类类是构造是构造DFADFA的一条的一条有效思路有效思路。例3-12构造DFA,接收 0,1,2,4,5,6,7,8,9 0,1,2,4,5,6,7,8,9上的语言，上的语言，该语言的每个字符串代表的数字该语言的每个字符串代表的数字能整除能整除3 3。仍仍然然只只使使用用3 3个个状状态态分分别别代代表表已已经经读读入入的的整整数数字字的的和和除除以以3 3的的不不同同的余数的情况：的余数的情况：状态与对应的等价类状态与对应的等价类q q0 0：余数为余数为0 0的输入串的等价类的输入串的等价类q q1

35、 1：余数为余数为1 1的输入串的等价类的输入串的等价类q q2 2：余数为余数为2 2的输入串的等价类的输入串的等价类例3-13构造DFA,接收00，11上的语言，该语言的每个字上的语言，该语言的每个字符串挡成符串挡成二进制数二进制数时，时，代表的数字能代表的数字能整除整除3 3。DFA DFA的每个状态对应一个等价类的每个状态对应一个等价类 利用一个状态去表示一个等价类利用一个状态去表示一个等价类 除以除以3 3的的余数只能为余数只能为0 0、1 1和和2 2q q0 0：余数为余数为0 0的输入串的等价类；的输入串的等价类；q q1 1：余数为余数为1 1的输入串的等价类；的输入串的等价

36、类；q q2 2：余数为余数为2 2的输入串的等价类；的输入串的等价类；不能接收空串，所以，不能接收空串，所以，还需要一个开始状态还需要一个开始状态q qS S人们习惯人们习惯使用十进制数使用十进制数w=x1x2x3xn(x1x2x3xn)2=(x1*2n-1+x2*2n-2+xn-1*2+xn)10当串长度增加当串长度增加1时：时：(x1x2x3xnxn+1)2=(x1*2n+x2*2n-1+xn-1*22+xn*2+xn+1)10=(2*(w)10+xn+1)10(w)10=3n+i(wx)10=(2*(w)10+x)10=6*n+2*i+x实际上实际上2*i+x对对3的余数就是的余数就是

37、wx对对3的余数的余数设设w是当前是当前已经读入已经读入的输入串；的输入串；qS：开始状态：开始状态读入读入0时，进入状态时，进入状态q0读入读入1时，进入状态时，进入状态q1q0能引导能引导DFA到达此状态的到达此状态的w除以除以3余数为余数为0，因此，因此(w)10=3n+0q0在此状态读入在此状态读入0，引导，引导DFA到达下到达下一状态的输入串为一状态的输入串为w0，则，则(w0)10=2(3n+0)+0=32n+0表明表明w0也属于也属于q0对应的等价类。对应的等价类。所以，所以，DFA在在q0状态读入状态读入0，应该继，应该继续保持续保持q0状态；状态；q0在此状态读入在此状态读入

38、1，引导，引导DFA到达到达下一状态的输入串为下一状态的输入串为w1，则，则(w1)10=2(3n+0)+1=32n+1表明表明w1属于属于q1对应的等价类。所以，对应的等价类。所以，DFA在在q0状态读入状态读入1，应该到达，应该到达q1状状态；态；q1能引导能引导DFA到达此状态的到达此状态的w除除以以3余数为余数为1，因此，因此(w)10=3n+1q1在此状态读入在此状态读入0，引导，引导DFA到达下到达下一状态的输入串为一状态的输入串为w0，则，则(w0)10=2(3n+1)+0=32n+2表明表明w0属于属于q2对应的等价类。所对应的等价类。所以，以，DFA在在q1状态读入状态读入0

39、，应该到，应该到达达q2状态；状态；q1在此状态读入在此状态读入1，引导，引导DFA到达下到达下一状态的输入串为一状态的输入串为w1，则，则(w1)10=2(3n+1)+1=32n+3表明表明w1属于属于q0对应的等价类。所对应的等价类。所以，以，DFA在在q1状态读入状态读入1，应该到，应该到达达q0状态；状态；q2能引导能引导DFA到达此状态的到达此状态的w除以除以3余数为余数为2，因此，因此，(w)10=3n+2q2在此状态读入在此状态读入0，引导，引导DFA到达下到达下一状态的输入串为一状态的输入串为w0，则，则(w0)10=2(3n+2)+0=32n+4表明表明w0属于属于q1对应的

40、等价类。所对应的等价类。所以，以，DFA在在q2状态读入状态读入0，应该到达，应该到达q1状态；状态；q2在此状态读入在此状态读入1，引导自动机到达，引导自动机到达下一状态的输入串为下一状态的输入串为w1，则，则(w1)10=2(3n+2)+1=32n+5表明表明w1属于属于q2对应的等价类。所对应的等价类。所以，自动机在以，自动机在q2状态读入状态读入1，继续保，继续保持持q2状态；状态；状态图状态图例3-14构造DFA，接收0，1上的语言，该语言的每个字上的语言，该语言的每个字符串为符串为二进制数二进制数时，时，代表的数字能被代表的数字能被5整除。整除。分析：分析：l对对5的余数只能为的余

41、数只能为0、1、2、3和和4l使用使用5个状态个状态分别代表已经读入的数字除分别代表已经读入的数字除以以5的不同的余数的等价类：的不同的余数的等价类：lqi：已经读入的数除以：已经读入的数除以5，余数为，余数为i的输入的输入串的等价类；串的等价类；l其中其中i=0,1,2,3,4l不能接收空串，需要一个开始状态不能接收空串，需要一个开始状态qS例3-15构造DFA，接收1,2,3上的语言，该语言的每上的语言，该语言的每个字符串挡成个字符串挡成十进制数十进制数时，时，代表的数字能被代表的数字能被4整除。整除。思考：思考：构造DFA，接收 0 0，1,21,2，3 3，4 4，5 5，6 6，7

42、7，8 8，99上的语言，该语言的每个字符串上的语言，该语言的每个字符串挡成挡成十进制十进制数时，数时，代表的数字能整除代表的数字能整除7 7。l总结：总结：构造DFA，接收=x=x1 1,x,x2 2,x,x3 3,x xm m 上的语言上的语言 该语言的每个字符串挡成该语言的每个字符串挡成basebase进进制数制数时时 代表的数字能整除代表的数字能整除N N 或或 代表的数字对代表的数字对N N的余数为的余数为K K分析：对对N N的的余余数数只只能能为为0 0、1 1、2 2、3 3、和和N-1N-1 使使用用N N个个状状态态分分别别代代表表已已经经读读入入的的串串（当当作作数数）对

43、对N N的的不不同同的的余余数数的等价类：的等价类：q q0 0：余数为：余数为0 0的输入串的等价类；的输入串的等价类；该类数十进制为该类数十进制为N*n+0N*n+0q q1 1：余数为：余数为1 1的输入串的等价类；该的输入串的等价类；该类数十进制为类数十进制为N*n+1N*n+1q q2 2：余数为：余数为2 2的输入串的等价类；该的输入串的等价类；该类数十进制为类数十进制为N*n+2N*n+2q qN-1N-1：余数为：余数为N-1N-1的输入串的等价类；的输入串的等价类；该类数十进制为该类数十进制为N*n+N-1N*n+N-1注意不能接收空串，不能接收空串，还需要一个还需要一个开始

44、状态开始状态q qS Sq qS S读入读入x x时，进入对应状态时，进入对应状态q qi i本质本质已知已知qi(i=0，1，2，N-1)x=x x=x1 1,x,x2 2,x,x3 3,x xm m应该如何确定应该如何确定j？qiqjxq qi i 已已经经读读入入的的数数为为w w，对对应应余余数数为为i i的输入串的等价类；的输入串的等价类；该类数十进制为该类数十进制为N*N*n+in+i 当当前前读读入入的的字字符符为为x x；则则wxwx表表示示的十进制数为的十进制数为(wx)10=base*base*(w)10+x+x =base*=base*（N*N*n+in+i）+x+x =

45、N*base*N*base*n+n+basebase*i+xi+x 该数对于该数对于N N取余数就是取余数就是base*base*i+xi+x对于对于N N的余数，的余数，若该余数为若该余数为j j，则相应的状态就应该从则相应的状态就应该从q qi i变换为变换为q qj j其中其中 i=0i=0，1 1，2 2，N-1N-1。x x=xx1 1,x,x2 2,x,x3 3,x xm m 0,10,1，base-1base-1例3-16构造DFA，接收 0 0，11上的语言上的语言 L=L=0 0n n1 1m m2 2k k|n,m,k=1|n,m,k=1 该该语语言言的的串串的的特特点点是

46、是，0 0在在最最前前面面，1 1在在中中间间，2 2在在最最后后，0 0、1 1和和2 2不能交叉不能交叉，顺序也，顺序也不能颠倒不能颠倒。0 0、1 1和和2 2的个数都至少为的个数都至少为1 1个；个；需要需要4 4个状态个状态：q q0 0：开始状态：开始状态,等待接收第等待接收第1 1个个0 0q q1 1：已经已经接收第接收第1 1个个0 0，负责负责接收可接收可能的多个能的多个0 0，等待等待接收第接收第1 1个个1 1；q q2 2：已经接收第已经接收第1 1个个1 1，负责接收可，负责接收可能的多个能的多个1 1，等待接收第，等待接收第1 1个个2 2；q q3 3：已经接收

47、第已经接收第1 1个个2 2，负责接收可，负责接收可能的多个能的多个2 2。状态转移图状态转移图(省略陷阱状态省略陷阱状态)q0010122q1q2q3思考思考1补充陷阱状态及对应的状态函数。补充陷阱状态及对应的状态函数。思考思考2DFADFA是否可以为是否可以为(省略陷阱状态省略陷阱状态)q0010122q1q2q3.4 .4 不确定的有限状态自动机不确定的有限状态自动机每个每个FSLFSL都是都是右线性语言右线性语言(定理定理3-13-1)问题问题 每个每个右线性语言右线性语言是不是一个是不是一个FSLFSL？例例接收语言接收语言 aaaa，abab 的的FAFA省略省略陷阱状陷阱状态态q

48、1abq0q2aaq3 该自动机接收的语言该自动机接收的语言L=L=aaaa，abab 是右线性语言；是右线性语言；但自动机但自动机不是不是DFADFA。(q(q0 0，a)=a)=qq1 1，q q2 2 即没有到达确定的惟一的状态。即没有到达确定的惟一的状态。不确定的有限状态自动机不确定的有限状态自动机-NFANFA3.4.1不确定的有限状态自动机不确定的有限状态自动机定义定义3-10NFA是一个五元式，是一个五元式，NFA=（Q，Q0，F）其中：其中：Q是一个有限状态的集合是一个有限状态的集合是字母表是字母表Q0 Q是是开始状态集合开始状态集合F Q是接收状态集合是接收状态集合是是Q2Q

49、的状态转换函数的状态转换函数即即(q，a)2QNFA在状态在状态q，扫描字母，扫描字母a后到达后到达可能可能的的下一下一状态集合状态集合。NFA与DFANFA有有一一个个可可能能的的开开始始状状态态集集合合和可能的下一和可能的下一状态集合状态集合其余的同其余的同DFA。NFA与与DFA的的重要区别重要区别在于在于转移函数转移函数的不同。的不同。(q，x)对应对应的是的是状态集合状态集合Q的一个的一个子集子集FA处于状态处于状态qDFA对对每个每个字母字母只有惟一的状态转移只有惟一的状态转移NFA对对某个某个字母字母可以有可以有多个状态转移多个状态转移；NFA接接收收该该字字母母时时,从从多多个

50、个状状态态转转移移中中可以可以非确定非确定地地选择选择任意一个任意一个。具体地具体地对于对于NFA，(q，a)Q(q，a)有有3种可能种可能(q，a)=(q，a)=q1(q，a)=q1，q2，qn或或或或(q，a)仍是一个仍是一个状态转换函数状态转换函数，只是其只是其值域值域发生了改变。发生了改变。所有所有(q，a)对应的所有子集元素对应的所有子集元素个数都为个数都为1时，时，NFA退化为退化为DFANFA停机停机NFANFA在两种情况下在两种情况下自动停机自动停机：将输入串扫描结束将输入串扫描结束 (q(q，a)=a)=(即即对对应应没没有有定定义义)或或在在扫扫描描一一个个串串w时时，NF