有限自动机理论精品文稿.ppt

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

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

2、，也是一个语言个语言第4页，本讲稿共173页统一的理论 形式语言与自动机作为统一的理论形式语言与自动机作为统一的理论,实际实际上包括上包括3个方面的内容个方面的内容:1)形式语言形式语言理论理论(产生语言产生语言)2)自动机自动机理论理论(接收语言接收语言)3)形式语言与自动机的形式语言与自动机的等价性等价性理论理论第5页，本讲稿共173页有限状态自动机有限状态自动机 FA(Finite state Automaton)FA是为研究是为研究 有限存储有限存储的计算过程的计算过程 正则语言正则语言而抽象出的一种计算模型。而抽象出的一种计算模型。第6页，本讲稿共173页两类有限状态自动机接收器接收

3、器 判断是否判断是否接收接收输入串；输入串；转换器转换器 对给定输入对给定输入产生输出产生输出。第7页，本讲稿共173页 FA还可以分成还可以分成确定（确定（DFA）与与非确非确定（定（NFA）两种。两种。第8页，本讲稿共173页等价性等价性 有限状态自动机识别的语言称为有限状态自动机识别的语言称为有限状态语言有限状态语言-FSL.从产生语言角度而言，从产生语言角度而言，FSL就是就是右线性语言右线性语言-RLL 从正则运算角度而言，从正则运算角度而言，FSL就就是是正则语言正则语言-RL。第9页，本讲稿共173页 有限状态自动机除了它在理论上的有限状态自动机除了它在理论上的价值外，价值外，还

4、在还在数字电路设计数字电路设计、词法分析词法分析、文文本编辑程序本编辑程序等领域得到广泛应用等领域得到广泛应用第10页，本讲稿共173页3.1 有限状态自动机有限状态自动机 有限状态自动机是具有有限状态自动机是具有离散离散输入和输输入和输出系统的一种出系统的一种数学模型数学模型。第11页，本讲稿共173页有限状态自动机有限状态自动机物理模型物理模型a1a2a3ajanan+1FSC第12页，本讲稿共173页 一个输入一个输入存储带（输入带）存储带（输入带），带被，带被分解为分解为单元单元，每个单元存放一个输入，每个单元存放一个输入符号符号(字母表上的符号字母表上的符号)。整个输入串从带的左端点

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

6、：读头读头读出读出带上当前单元的字符带上当前单元的字符 FSC根据当前根据当前FSC的状态和读出的的状态和读出的字符，字符，进行进行状态改变状态改变；将读头将读头向右移动向右移动一个单元。一个单元。第16页，本讲稿共173页有限态自动机的动作有限态自动机的动作简化简化为：为：FSC根据根据 当前状态当前状态 和和 当前读取的带上当前读取的带上字符字符 进行进行状态改变状态改变。第17页，本讲稿共173页定义定义3-1 有限状态自动机有限状态自动机FAFA是一个五元式是一个五元式 FA=(Q，q0，F)Q是有限状态的集合是有限状态的集合 是字母表，也就是输入带上的是字母表，也就是输入带上的字符的

7、集合；字符的集合；第18页，本讲稿共173页 q0Q是开始状态；是开始状态；F Q是接收状态是接收状态(终止状态终止状态)集合；集合；第19页，本讲稿共173页是是QQ的状态转换函数，的状态转换函数，即即(q，x)=q 代表自动机在状态代表自动机在状态q时，扫描字符时，扫描字符x后后到达状态到达状态q第20页，本讲稿共173页 有限状态自动机的状态转换函数的有限状态自动机的状态转换函数的个数应该为个数应该为|Q|*|对于对于Q中的每个中的每个状态状态，都应该定，都应该定义对应义对应的每个的每个字母字母的的状态转换状态转换。第21页，本讲稿共173页DFA 这种有限状态自动机为这种有限状态自动机

8、为确定的有限确定的有限状态自动机状态自动机DFA。第22页，本讲稿共173页例3-1DFA=(q0,q1,0,1,q0,q0)其中其中：第23页，本讲稿共173页的表示：函数形式(q0，0)=q1(q0，1)=q1(q1，0)=q1(q1，1)=q0第24页，本讲稿共173页的表示：状态矩阵 Q 0q01q1q1q1q1q0第25页，本讲稿共173页的表示:状态图形式状态图是一个状态图是一个有向有向、有、有循环循环的图的图 一个节点表示一个状态；若有一个节点表示一个状态；若有(q，x)=q，则，则状态状态q到状态到状态q有一条有一条有向边有向边，并用，并用字母字母x作标记。作标记。第26页，本

9、讲稿共173页的表示 指向的状态是开始状态指向的状态是开始状态 两个圆圈两个圆圈代表代表接收状态接收状态；第27页，本讲稿共173页的表示：状态图状态图q11010q0第28页，本讲稿共173页 用状态图表示一个用状态图表示一个DFADFA 有向边的有向边的数目数目就是状态转换函数的个就是状态转换函数的个数。数。第29页，本讲稿共173页3.2 3.2 有限状态自动机识别语言有限状态自动机识别语言对于对于DFADFA，给定串，给定串w=xw=x1 1x x2 2xxn n；初始时，初始时，DFADFA处于开始状态处于开始状态q q0 0 从左到右逐个字符地扫描串从左到右逐个字符地扫描串w w第

10、30页，本讲稿共173页 在在(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 第31页，本讲稿共173页当将串当将串w w扫描结束扫描结束后，后，若若DFADFA处于某一个处于某一个接收状态接收状态，则有限状态自动机能够则有限状态自动机能够接收接收串串w w第32页，本讲稿共173页对于对于可接收串可接收串DFADFA从从开开始始状状态态开开始始，在在扫扫描描串串的的过过程中，程中，状态逐个地变化状态逐个地变化,串扫描结束后

11、，串扫描结束后，到达到达某个某个接收状态接收状态。第33页，本讲稿共173页对于对于不可接收串不可接收串DFADFA从从开开始始状状态态开开始始，在在扫扫描描串串的的过过程程中，中，状态逐个地变化状态逐个地变化,串扫描结束后，串扫描结束后，处于处于非接收状态非接收状态。第34页，本讲稿共173页对于字母表对于字母表上的上的DFADFA 能识别的所有串的集合，就是能识别的所有串的集合，就是DFADFA能接收的语言能接收的语言:L(DFA)L(DFA)也称为有限状态语言（也称为有限状态语言（FSLFSL）第35页，本讲稿共173页思考思考如何如何形式化形式化定义定义L(DFA)L(DFA)?第36

12、页，本讲稿共173页定义3-4 扩展的状态转换函数给给定定DFADFA，扩扩展展的的状状态态转转换换函函数数*：QQ*QQ 即即 *(q,(q,w w)=q)=q即即DFADFA在在一一个个状状态态q q时时，扫扫描描串串w w后后到到达唯一达唯一确定确定的状态的状态qq第37页，本讲稿共173页递归扩展的状态转换函数 *(q q,)=,)=q q；*(q,a)=(q,a)(q,a)=(q,a)其中其中a a；第38页，本讲稿共173页对于串对于串w=w=a a（+）*（q q，w w）=*(q(q，a a）=(*(q,(q,),),a a)第39页，本讲稿共173页或者或者 对于串对于串w=

13、w=a a *(q(q，w w)=*(q(q，a a)=*(q(q，a a),),)第40页，本讲稿共173页定义定义3-6 DFA3-6 DFA接收的语言接收的语言DFA=(Q,qDFA=(Q,q0 0，F)F)接收的语言接收的语言 L(DFA)=w|L(DFA)=w|*(q(q0 0,w),w)FF第41页，本讲稿共173页思考思考如何描述如何描述 在某个在某个时刻时刻，DFA所处的情况？所处的情况？第42页，本讲稿共173页定义定义3-7 DFA3-7 DFA的瞬时描述（格局）的瞬时描述（格局）格局是一个二元式：格局是一个二元式：q qy y q q是是DFADFA当前状态当前状态 y

14、y是输入带上还没有被扫描到的串是输入带上还没有被扫描到的串 读头将扫描读头将扫描y y串的第串的第1 1个符号个符号第43页，本讲稿共173页 在在扫扫描描串串的的过过程程中中，格格局局在在发发生生转转换换(改变改变)格格局局的的(一一次次)转转换换的的原原因因是是由由于于函数函数的的(一次一次)作用作用第44页，本讲稿共173页 如果当前格局为：如果当前格局为：q qa ar r 有有函数：函数：(q(q，a)=qa)=q 则下一格局为：则下一格局为：qrqr ；格局的转换可以记为：格局的转换可以记为：qar qar=qr qr；第45页，本讲稿共173页DFA的特殊格局初始格局为：初始格局

15、为：q q0 0w w接收格局为：接收格局为：q qf f其中，其中，q qf f是某个接收状态是某个接收状态 第46页，本讲稿共173页使用使用=*代表格局的代表格局的任意次任意次转换转换使用使用=+代表格局的代表格局的多次多次转换转换第47页，本讲稿共173页可以使用可以使用格局的转换格局的转换方式定义方式定义FSLFSL第48页，本讲稿共173页DFADFA接收的语言接收的语言 L(DFA)=L(DFA)=w|q w|q0 0w=w=*q qf f；ww*且且q qf fFF第49页，本讲稿共173页定义3-8 DFA停机DFA将输入串扫描结束时将输入串扫描结束时 (自动自动)停机停机第

16、50页，本讲稿共173页注意1：DFA将输入串扫描结束停机时，将输入串扫描结束停机时，如果如果DFA处于某一个处于某一个接收状态接收状态，则则表示接收整个输入串；表示接收整个输入串；反之，则表示反之，则表示不接收不接收整个输入串整个输入串;第51页，本讲稿共173页注意2：对于状态对于状态q,如果如果不能识别不能识别字母字母a 则将状态转换到一个特殊的状态：则将状态转换到一个特殊的状态：陷阱状态陷阱状态qt 即即 (q，a)=qt第52页，本讲稿共173页 陷阱陷阱状态状态qt不能够改变为其他状态不能够改变为其他状态 即即 对于对于a (qt，a)=qt第53页，本讲稿共173页构造构造DFA

17、，分别接收语言，分别接收语言0，1*0，1+0 =0=0 01第54页，本讲稿共173页定理3-1 每个每个FSLFSL都是一个都是一个右线性语言右线性语言分析：分析：已知已知 接收接收FSL的的DFA 构造构造 右线性文法右线性文法产生该产生该FSL第55页，本讲稿共173页证明思路证明思路状态转换函数和产生式的状态转换函数和产生式的等价等价作用作用 (q,a)=q AaB 接收接收a 产生产生a 状态状态变化变化 非终结符号非终结符号变化变化结论结论:DFA:DFA状态状态等价于文法等价于文法非终结符非终结符第56页，本讲稿共173页思考思考 DFA的接收状态的作用的接收状态的作用第57页

18、，本讲稿共173页证明假设假设L L是字母表是字母表上的上的FSLFSL，则，则 L=L(DFA)L=L(DFA)第58页，本讲稿共173页 DFA=DFA=（Q Q，q q0 0，F F）构造构造右线性右线性文法文法G=(,G=(,Q,Q,q q0 0，P P）其中其中P P为：为：第59页，本讲稿共173页 qaqqaq|(q|(q，a)=qa)=q U U qqa a|(q|(q，a)Fa)F 特别，若特别，若q q0 0是接收状态，则是接收状态，则 q q0 0第60页，本讲稿共173页对于串w=x1x2xn：DFA：则文法有则文法有(q0,x1)=q1 q0 x1q1；(q1,x2)

19、=q2 q1x2q2；(qn-2,xn-1)=qn-1 qn-2xn-1qn-1(qn-1,xn)=qn qn-1xnqn 或或 qn-1xn 第61页，本讲稿共173页所以 DFA 文法文法*(q，)=q q=*q*(q0，w)F q0=*w第62页，本讲稿共173页例例3-2 DFA与文法的转换与文法的转换FSLFSL=(0,1)1=(0,1)1*00*接收该语言的接收该语言的DFADFA为：为：第63页，本讲稿共173页q11001q0第64页，本讲稿共173页构造构造正则正则文法产生该语言：文法产生该语言：q00q1|1q1|q10q0|1q1|0第65页，本讲稿共173页定理定理3-

20、2FSL对对补补运算封闭运算封闭第66页，本讲稿共173页证明：设设L L1 1是是上的上的FSL,FSL,且且L L1 1=L(DFA=L(DFA1 1)，DFA DFA1 1=（Q Q，q q0 0，F F）第67页，本讲稿共173页构造构造 DFA DFA2 2=（Q Q，q q0 0，Q Q）DFADFA2 2接收的语言是接收的语言是 L L1 1的对应的全集的对应的全集,即即*第68页，本讲稿共173页构造构造 DFA DFA3 3=(Q=(Q，q q0 0，Q-FQ-F)DFA DFA3 3接收的语言是接收的语言是L L1 1的的补补 L L3 3=L(DFA=L(DFA3 3)也

21、是也是FSLFSL语言。语言。第69页，本讲稿共173页注意此时的此时的DFADFA1 1的的函数的个数为函数的个数为|Q|Q|*|第70页，本讲稿共173页基本的等价替换基本的等价替换l对于状态转换图，有基本的等价替换对于状态转换图，有基本的等价替换l变换为00,11第71页，本讲稿共173页3.3 DFA3.3 DFA识别语言的例子识别语言的例子 构造构造DFA，接收语言接收语言 L=ab 第72页，本讲稿共173页基本结构（接收基本句子）基本结构（接收基本句子）q1abq0q2第73页，本讲稿共173页增加增加陷阱状态陷阱状态后的后的DFADFAq1abq0qtbaa,ba,bq2第74

22、页，本讲稿共173页思考思考1 1 如如果果将将该该DFADFA的的所所有有状状态态都都设设置置为为接收状态接收状态(包括陷阱状态包括陷阱状态)，接收的语言是接收的语言是？第75页，本讲稿共173页思考思考2 2 如如果果将将该该自自动动机机的的接接收收状状态态和和非非接接收收状态对调状态对调 接收的语言是接收的语言是？第76页，本讲稿共173页例3-4构造DFA识别语言识别语言L=L=x000yx000y|x,y0,1|x,y0,1*第77页，本讲稿共173页分析 该语言的特点是该语言的特点是 语语言言中中的的每每个个串串都都包包含含连连续续的的3 3个个0 0（即每个串都包含子串（即每个串

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

24、00。第81页，本讲稿共173页由由于于字字符符是是逐逐一一读读入入的的，当当从从输输入入串串中读入一个中读入一个0 0时，时，它它有可能有可能是是000000的的第第1 1个个0 0，需要需要记住记住已经出现过一个已经出现过一个0 0；第82页，本讲稿共173页如果紧接着读入的是字符如果紧接着读入的是字符1 1，则刚读入的则刚读入的0 0就不是就不是000000的第的第1 1个个0 0需要需要重新寻找重新寻找000000子串的第子串的第1 1个个0 0；第83页，本讲稿共173页如如果果紧紧接接着着读读入入的的还还是是0 0，它它有有可可能能是是000000的的第第2 2个个0 0，也需要也

25、需要记住记住这个这个0 0，继续读入字符，若是继续读入字符，若是0 0，则，则发现发现000000否则，需要否则，需要重新重新寻找寻找000000。第84页，本讲稿共173页初始状态：初始状态：q q0 0接收接收0 0，到达状态，到达状态q q1 1接收接收00,00,到达状态到达状态q q2 2接收接收000,000,到达状态到达状态q q3 3第85页，本讲稿共173页因此，因此，基本的基本的状态转移函数为：状态转移函数为：(q(q0 0，0)=q0)=q1 1 (q (q1 1，0)=q0)=q2 2 (q (q2 2，0)=q0)=q3 3用于接收基本句子用于接收基本句子000000

26、第86页，本讲稿共173页接收接收000000的状态图的状态图q0000q1q2q3第87页，本讲稿共173页其他状态转移函数为：其他状态转移函数为：(q(q0 0，1)=q1)=q0 0 期待期待0 0的出现的出现 (q(q1 1，1)=q1)=q0 0 重新寻找重新寻找000000 (q(q2 2，1)=q1)=q0 0 重新寻找重新寻找000000 (q (q3 3，0)=q0)=q3 3 扫描后续字符扫描后续字符 (q (q3 3，1)=q1)=q3 3 扫描后续字符扫描后续字符第88页，本讲稿共173页状态转移图状态转移图q00111000,1q1q2q3第89页，本讲稿共173页思

27、考思考如果需要接收语言如果需要接收语言 L 如何修改有限状态自动机如何修改有限状态自动机?思路：思路：考虑考虑开始状态开始状态的作用的作用第90页，本讲稿共173页思考思考:如果如果 DFA的的开始状态开始状态只负责识别输入串只负责识别输入串的第一个字母；的第一个字母；文法的文法的开始符号开始符号只负责串的推导的只负责串的推导的开始；开始；优点是？优点是？第91页，本讲稿共173页状态图为状态图为10qs01000,1q1q2q3q011第92页，本讲稿共173页例3-5构造DFA 识别语言识别语言 L=L=x x001001y y|x|x，y0y0，11*第93页，本讲稿共173页分析：对于

28、任何输入串，对于任何输入串，DFADFA的任务就是的任务就是要检查该输入串中是否存在要检查该输入串中是否存在001001 第94页，本讲稿共173页初始状态：初始状态：q q0 0q q1 1 已接收已接收0 0q q2 2 已接收已接收00 00 q q3 3 已接收已接收001 001 第95页，本讲稿共173页q2q1q0状态转移图状态转移图01q31010,10第96页，本讲稿共173页例3-6 构造DFA识别语言识别语言L=L=x x000000|x0|x0，11*第97页，本讲稿共173页q2q3q1q001110001第98页，本讲稿共173页例3-7构造DFA识别语言识别语言L

29、=L=x x000000 x x001001其中，其中，x0 x0，11*第99页，本讲稿共173页q2q1q001q310001q4101第100页，本讲稿共173页例3-8构造DFA识别语言识别语言L=L=0 02k+3m2k+3m|m,k=0|m,k=0 第101页，本讲稿共173页实际上：实际上：2k+3m2k+3m可以表示任意的可以表示任意的非负整数非负整数(除除1 1外外)该语言为该语言为0*-0 第102页，本讲稿共173页状态转移图状态转移图000q1q2q0第103页，本讲稿共173页思考：构造DFA识别语言识别语言L=0L=02k+3m2k+3m|m,k0m,k0 考查题考

30、查题 1第104页，本讲稿共173页例3-9构造DFA 识别识别00，11上的语言，该语言的上的语言，该语言的 每个句子以每个句子以0 0开头，以开头，以1 1结尾。结尾。第105页，本讲稿共173页状态转移图状态转移图010q1q210qt0,11q0第106页，本讲稿共173页例3-10 构造DFA识别识别00，11上的语言，该语言的每个上的语言，该语言的每个字符串字符串 不包含不包含0000子串子串(语言允许语言允许)第107页，本讲稿共173页000,1qtq1q0q21011第108页，本讲稿共173页或或000,1qtq1q011第109页，本讲稿共173页构造DFA识别识别00，

31、11上的语言，上的语言，该语言的每个字符串不包含该语言的每个字符串不包含0000（语言不允许语言不允许 ）第110页，本讲稿共173页例3-11构造DFA识别识别00，1 1，22上的语言，上的语言，该语言的每个字符串代表的数字该语言的每个字符串代表的数字能整除能整除3 3。第111页，本讲稿共173页分析 如如果果一一个个十十进进制制整整数数的的所所有有位位的的数数字的和字的和能够整除能够整除3 3，那么，那么，这个十进制整数就能够整除这个十进制整数就能够整除3 3；第112页，本讲稿共173页一一个个十十进进制制整整数数除除以以3 3，余余数数只只能能是是1 1、2 2和和0 0；第113

32、页，本讲稿共173页 将将整整数数当当作作一一个个字字符符串串，从从左左到到右右逐一地读入；逐一地读入；使使用用3 3个个状状态态分分别别代代表表已已读读入入的的数数字的字的和和除以除以3 3的的余数情况余数情况：(即读入的整数对即读入的整数对3 3的余数情况）的余数情况）第114页，本讲稿共173页q q0 0：已已读入的整数除以读入的整数除以3 3，余数为余数为0 0q q1 1：已已读入的整数除以读入的整数除以3 3，余数为余数为1 1q q2 2：已已读入的整数除以读入的整数除以3 3，余数为余数为2 2第115页，本讲稿共173页思考思考 已知已知qi(i=0,1,2)，n=0,1,

33、2，应该如何确定应该如何确定 j？qiqjn第116页，本讲稿共173页 扫描子串扫描子串w w后后,处于某个状态处于某个状态q qi i，读入当前数字读入当前数字,状态转换情况为状态转换情况为第117页，本讲稿共173页q0l在在此此状状态态读读入入0 0，引引导导DFADFA到到达达下下一一状态的输入串为状态的输入串为w0w0,lw0w0的的各各位位数数字字和和除除以以3 3，余余数数为为0 0。所所以以，DFADFA在在q q0 0状状态态读读入入0 0，应应该该继继续保持续保持q q0 0状态；状态；第118页，本讲稿共173页q0l在在此此状状态态读读入入1 1，引引导导DFADFA

34、到到达达下下一一状状态态的的输输入入串串为为w1w1，w1w1的的各各位位数数字字和除以和除以3 3，余数为余数为1 1。l所所以以，DFADFA在在q q0 0状状态态读读入入1 1，应应该该到到达达q q1 1状态；状态；第119页，本讲稿共173页q0l在此状态读入在此状态读入2 2，引导，引导DFADFA到达下一到达下一状态的输入串为状态的输入串为w2w2，w2w2的各位数字的各位数字和除以和除以3 3，余数为余数为2 2。l所以，所以，DFADFA在在q q0 0状态读入状态读入2 2，应该到，应该到达达q q2 2状态；状态；l第120页，本讲稿共173页第121页，本讲稿共173

35、页存在的问题 接收的串包括以接收的串包括以0开始开始的数字串；的数字串；还能够接收还能够接收空串空串第122页，本讲稿共173页思考如何进行改进，使得如何进行改进，使得 接收的串不能以接收的串不能以0开始，开始，不能接收不能接收空串空串。第123页，本讲稿共173页定义3-9 set集合对于状态对于状态q，能将，能将DFA从从q0转换到转换到q状状态的所有字符串的集合为：态的所有字符串的集合为：set(q)set(q)=w|w=w|w*,*(q(q0 0,w)=q,w)=q 第124页，本讲稿共173页则则有限状态自动机有限状态自动机DFADFA接收的接收的语言可语言可以定义为：以定义为：L(

36、DFA)=set(q)其中：其中：q qFF第125页，本讲稿共173页按状态进行划分按状态进行划分对于对于DFADFA，可以定义关系可以定义关系R R 若若 x,yx,y*，qQ qQ 则则 xRy xRy 当且仅当当且仅当 xset(q),yset(q)xset(q),yset(q)第126页，本讲稿共173页 该该关关系系是是集集合合*上上的的一一个个等等价价关关系系，利用该关系，利用该关系，可可以以将将*划划分分为为不不多多于于|Q|Q|个个的的等等价类价类。第127页，本讲稿共173页 DFADFA可可以以按按照照语语言言的的特特点点给给出出字字母母表表*的的一一个个划划分分，这这种

37、种划划分分相相当当于于*上的一个等价分类。上的一个等价分类。DFA DFA每个每个状态状态对应着一个对应着一个等价类等价类第128页，本讲稿共173页 利用一个利用一个状态状态去表示一个去表示一个等价类等价类是构造是构造DFADFA的一条的一条有效思路有效思路。第129页，本讲稿共173页例3-12构造DFA,识别 0,1,2,4,5,6,7,8,9 0,1,2,4,5,6,7,8,9上的语言，上的语言，该语言的每个字符串代表的数字能整该语言的每个字符串代表的数字能整除除3 3。第130页，本讲稿共173页 仍仍然然只只使使用用3 3个个状状态态分分别别代代表表已已经经读读入入的的整整数数字字

38、的的和和除除以以3 3的的不不同同的的余余数数的情况：的情况：第131页，本讲稿共173页状态与对应的等价类状态与对应的等价类q q0 0：余数为余数为0 0的输入串的等价类的输入串的等价类q q1 1：余数为余数为1 1的输入串的等价类的输入串的等价类q q2 2：余数为余数为2 2的输入串的等价类的输入串的等价类第132页，本讲稿共173页第133页，本讲稿共173页例3-13构造DFA,识别00，11上的语言，该语言的每个字符上的语言，该语言的每个字符串挡成串挡成二进制数二进制数时，时，代表的数字能代表的数字能整除整除3 3。第134页，本讲稿共173页 DFA DFA的每个状态对应一个

39、等价类的每个状态对应一个等价类 利用一个状态去表示一个等价类利用一个状态去表示一个等价类 除以除以3 3的的余数只能为余数只能为0 0、1 1和和2 2第135页，本讲稿共173页q q0 0：余数为余数为0 0的输入串的等价类；的输入串的等价类；q q1 1：余数为余数为1 1的输入串的等价类；的输入串的等价类；q q2 2：余数为余数为2 2的输入串的等价类；的输入串的等价类；第136页，本讲稿共173页不能接收空串，所以，不能接收空串，所以，还需要一个开始状态还需要一个开始状态q qS S第137页，本讲稿共173页设设w是当前读入的输入串；是当前读入的输入串；qS：在开始状态：在开始状

40、态读入读入0时，时，w=0，进入状态，进入状态q0；读入读入1时，时，w=1，进入状态，进入状态q1；第138页，本讲稿共173页q0 能引导能引导DFA到达此状态的到达此状态的w除以除以3余余数为数为0，因此，因此 (w)10=3n+0第139页，本讲稿共173页q0 在此状态读入在此状态读入0，引导，引导DFA到达下一到达下一状态的输入串为状态的输入串为w0，则，则 (w0)10=2(3n+0)+0=32n+0 表明表明w0也属于也属于q0对应的等价类。所对应的等价类。所以，以，DFA在在q0状态读入状态读入0，应该继续，应该继续保持保持q0状态；状态；第140页，本讲稿共173页q0 在

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

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

43、173页q2 在此状态读入在此状态读入0，引导，引导DFA到达下一到达下一状态的输入串为状态的输入串为w0，则，则 (w0)10=2(3n+2)+0=32n+4 表明表明w0属于属于q1对应的等价类。所以，对应的等价类。所以，DFA在在q2状态读入状态读入0，应该到达，应该到达q1状态；状态；第146页，本讲稿共173页q2 在此状态读入在此状态读入1，引导自动机到达下，引导自动机到达下一状态的输入串为一状态的输入串为w1，则，则(w1)10=2(3n+2)+1=32n+5 表明表明w1属于属于q2对应的等价类。所以，对应的等价类。所以，自动机在自动机在q2状态读入状态读入1，继续保持，继续保

44、持q2状状态；态；第147页，本讲稿共173页状态图状态图第148页，本讲稿共173页例3-14构造DFA，识别 0，1上的语言，该语言的每个字符上的语言，该语言的每个字符串为串为二进制数二进制数时，时，代表的数字能被代表的数字能被5整除。整除。第149页，本讲稿共173页分析：分析：l对对5的余数只能为的余数只能为0、1、2、3和和4l使用使用5个状态个状态分别代表已经读入的数字除以分别代表已经读入的数字除以5的不同的余数的等价类：的不同的余数的等价类：lqi：已经读入的数除以：已经读入的数除以5，余数为，余数为i的输入串的输入串的等价类；的等价类；l其中其中 i=0,1,2,3,4l不能接

45、收空串，需要一个开始状态不能接收空串，需要一个开始状态qS第150页，本讲稿共173页第151页，本讲稿共173页例3-15构造DFA，识别 1,2,3上的语言，该语言的每个上的语言，该语言的每个字符串挡成字符串挡成十进制数十进制数时，时，代表的数字能被代表的数字能被4整除。整除。第152页，本讲稿共173页第153页，本讲稿共173页思考：思考：构造DFA，识别 0 0，1,21,2，3 3，4 4，5 5，6 6，7 7，8 8，99上上的语言，该语言的每个字符串挡成的语言，该语言的每个字符串挡成十十进制进制数时，数时，代表的数字能整除代表的数字能整除7 7。l第154页，本讲稿共173页

46、总结：总结：构造DFA，识别=x=x1 1,x,x2 2,x,x3 3,x xm m 上的语言上的语言 该语言的每个字符串挡成该语言的每个字符串挡成basebase进制进制数数时时 代表的数字能整除代表的数字能整除N N。或或 对对N N的余数为的余数为K K。第155页，本讲稿共173页分析：对对N N的的余余数数只只能能为为0 0、1 1、2 2、3 3、和和N-1N-1。使使用用N N个个状状态态分分别别代代表表已已经经读读入入的的数数对对N N的不同的余数的等价类：的不同的余数的等价类：第156页，本讲稿共173页q q0 0：余数为：余数为0 0的输入串的等价类；的输入串的等价类；该

47、类数十进制为该类数十进制为N*n+0N*n+0第157页，本讲稿共173页q q1 1：余数为：余数为1 1的输入串的等价类；该类的输入串的等价类；该类数十进制为数十进制为N*n+1N*n+1q q2 2：余数为：余数为2 2的输入串的等价类；该类的输入串的等价类；该类数十进制为数十进制为N*n+2N*n+2第158页，本讲稿共173页q qN-1N-1：余数为：余数为N-1N-1的输入串的等价类；的输入串的等价类；该类数十进制为该类数十进制为N*n+N-1N*n+N-1第159页，本讲稿共173页注意不能接收空串，不能接收空串，还需要一个还需要一个开始状态开始状态q qS S第160页，本讲

48、稿共173页q qS S读入读入x x时，进入对应状态时，进入对应状态q qi i第161页，本讲稿共173页本质本质 已知已知qi(i=0，1，2，N-1)x=x x=x1 1,x,x2 2,x,x3 3,x xm m 应该如何确定应该如何确定 j？qiqjx第162页，本讲稿共173页q qi i 已已经经读读如如的的数数字字为为w w，对对应应余余数数为为i i的输入串的等价类；的输入串的等价类；该类数十进制为该类数十进制为N*n+iN*n+i第163页，本讲稿共173页 当当前前读读入入的的字字符符为为x x；则则wxwx表表示示的的十进制数为十进制数为 base*base*（N*n+

49、iN*n+i）+x+x =N*base*n+N*base*n+base*i+xbase*i+x第164页，本讲稿共173页 该数对于该数对于N N取余数就是取余数就是base*i+xbase*i+x对对于于N N的余数，的余数，若该余数为若该余数为j j，则相应的状态就应该从则相应的状态就应该从q qi i变换为变换为q qj j第165页，本讲稿共173页其中其中 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第166页，本讲稿共173页例3-16构造DFA，识别 0 0，11上的语言

50、上的语言 L=L=0 0n n1 1m m2 2k k|n,m,k=1|n,m,k=1第167页，本讲稿共173页 该该语语言言的的串串的的特特点点是是，0 0在在最最前前面面，1 1在在中中间间，2 2在在最最后后，0 0、1 1和和2 2不不能能交交叉叉，顺序也，顺序也不能颠倒不能颠倒。0 0、1 1和和2 2的个数都至少为的个数都至少为1 1个；个；需要需要4 4个状态个状态：第168页，本讲稿共173页q q0 0：开始状态：开始状态,等待接收第等待接收第1 1个个0 0q q1 1：已经已经接收第接收第1 1个个0 0，负责负责接收可能接收可能的多个的多个0 0，等待等待接收第接收第