《有限自动机理论幻灯片.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论幻灯片.ppt（173页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、有限自动机理论第1页，共173页，编辑于2022年，星期六定义语言可以从两个方面可以从两个方面进行进行：）从）从产生产生语言的角度；语言的角度；）从）从接收接收(或识别或识别)语言的角度。语言的角度。第2页，共173页，编辑于2022年，星期六形式语言研究内容形式语言研究内容产生产生一个语言一个语言:1)定义语言中的定义语言中的基本句子基本句子;2)根据根据其余句子其余句子的的形成规则形成规则，产生产生出出该语言所包含的所有该语言所包含的所有句子句子。第3页，共173页，编辑于2022年，星期六有限自动机有限自动机研究内容研究内容 使用某种使用某种自动机模型自动机模型来接收字符串来接收字符串
2、接收接收的所有字符串形成的集合，也是的所有字符串形成的集合，也是一个语言一个语言第4页，共173页，编辑于2022年，星期六统一的理论 形式语言与自动机作为统一的理论形式语言与自动机作为统一的理论,实际实际上包括上包括3个方面的内容个方面的内容:1)形式语言形式语言理论理论(产生语言产生语言)2)自动机自动机理论理论(接收语言接收语言)3)形式语言与自动机的形式语言与自动机的等价性等价性理论理论第5页，共173页，编辑于2022年，星期六有限状态自动机有限状态自动机 FA(Finite state Automaton)FA是为研究是为研究 有限存储有限存储的计算过程的计算过程 正则语言正则语言
3、而抽象出的一种计算模型。而抽象出的一种计算模型。第6页，共173页，编辑于2022年，星期六两类有限状态自动机接收器接收器 判断是否判断是否接收接收输入串；输入串；转换器转换器 对给定输入对给定输入产生输出产生输出。第7页，共173页，编辑于2022年，星期六 FA还可以分成还可以分成确定（确定（DFA）与与非确非确定（定（NFA）两种。两种。第8页，共173页，编辑于2022年，星期六等价性等价性 有限状态自动机识别的语言称为有限状态自动机识别的语言称为有限状态语言有限状态语言-FSL.从产生语言角度而言，从产生语言角度而言，FSL就是就是右线性语言右线性语言-RLL 从正则运算角度而言，从
4、正则运算角度而言，FSL就是就是正则语言正则语言-RL。第9页，共173页，编辑于2022年，星期六 有限状态自动机除了它在理论上的有限状态自动机除了它在理论上的价值外，价值外，还在还在数字电路设计数字电路设计、词法分析词法分析、文文本编辑程序本编辑程序等领域得到广泛应用等领域得到广泛应用第10页，共173页，编辑于2022年，星期六3.1 有限状态自动机有限状态自动机 有限状态自动机是具有有限状态自动机是具有离散离散输入和输输入和输出系统的一种出系统的一种数学模型数学模型。第11页，共173页，编辑于2022年，星期六有限状态自动机有限状态自动机物理模型物理模型a1a2a3aj anan+1
5、FSC第12页，共173页，编辑于2022年，星期六 一个输入一个输入存储带（输入带）存储带（输入带），带被，带被分解为分解为单元单元，每个单元存放一个输入，每个单元存放一个输入符号符号(字母表上的符号字母表上的符号)。整个输入串从带的左端点开始存放，整个输入串从带的左端点开始存放，而带的右端可以而带的右端可以无限扩充无限扩充；第13页，共173页，编辑于2022年，星期六 一个有穷状态控制器（一个有穷状态控制器（FSC）该控制器的状态只能是有限多个该控制器的状态只能是有限多个 FSC通过一个通过一个读头读头读出读出当前带上单当前带上单元的字符。元的字符。第14页，共173页，编辑于2022年
6、，星期六 初始时，读头对应带的初始时，读头对应带的最左单元最左单元，每读出一个字符，读头每读出一个字符，读头向右向右自动自动移动一个单元。移动一个单元。读头读头(暂时暂时)不不允许允许向左移动向左移动。第15页，共173页，编辑于2022年，星期六有限状态自动机的一个动作为：有限状态自动机的一个动作为：读头读头读出读出带上当前单元的字符带上当前单元的字符 FSC根据当前根据当前FSC的状态和读出的的状态和读出的字符，字符，进行进行状态改变状态改变；将读头将读头向右移动向右移动一个单元。一个单元。第16页，共173页，编辑于2022年，星期六有限态自动机的动作有限态自动机的动作简化简化为：为：F
7、SC根据根据 当前状态当前状态 和和 当前读取的带上当前读取的带上字符字符 进行进行状态改变状态改变。第17页，共173页，编辑于2022年，星期六定义定义3-1 有限状态自动机有限状态自动机FAFA是一个五元式是一个五元式 FA=(Q，q0，F)Q是有限状态的集合是有限状态的集合 是字母表，也就是输入带上的是字母表，也就是输入带上的字符的集合；字符的集合；第18页，共173页，编辑于2022年，星期六 q0Q是开始状态；是开始状态；F Q是接收状态是接收状态(终止状态终止状态)集合；集合；第19页，共173页，编辑于2022年，星期六是是QQ的状态转换函数，的状态转换函数，即即(q，x)=q
8、 代表自动机在状态代表自动机在状态q时，扫描字符时，扫描字符x后到达状态后到达状态q第20页，共173页，编辑于2022年，星期六 有限状态自动机的状态转换函有限状态自动机的状态转换函数的个数应该为数的个数应该为|Q|*|对于对于Q中的每个中的每个状态状态，都应该定，都应该定义对应义对应的每个的每个字母字母的的状态转换状态转换。第21页，共173页，编辑于2022年，星期六DFA 这种有限状态自动机为这种有限状态自动机为确定的有限确定的有限状态自动机状态自动机DFA。第22页，共173页，编辑于2022年，星期六例3-1DFA=(q0,q1,0,1,q0,q0)其中其中：第23页，共173页，
9、编辑于2022年，星期六的表示：函数形式(q0，0)=q1(q0，1)=q1(q1，0)=q1(q1，1)=q0第24页，共173页，编辑于2022年，星期六的表示：状态矩阵 Q 0q01q1q1q1q1q0第25页，共173页，编辑于2022年，星期六的表示:状态图形式状态图是一个状态图是一个有向有向、有、有循环循环的图的图 一个节点表示一个状态；若有一个节点表示一个状态；若有(q，x)=q，则，则状态状态q到状态到状态q有一条有一条有向边有向边，并用，并用字母字母x作标记。作标记。第26页，共173页，编辑于2022年，星期六的表示 指向的状态是开始状态指向的状态是开始状态 两个圆圈两个圆
10、圈代表代表接收状态接收状态；第27页，共173页，编辑于2022年，星期六的表示：状态图状态图q11010q0第28页，共173页，编辑于2022年，星期六 用状态图表示一个用状态图表示一个DFADFA 有向边的有向边的数目数目就是状态转换函数的就是状态转换函数的个数。个数。第29页，共173页，编辑于2022年，星期六3.2 3.2 有限状态自动机识别语言有限状态自动机识别语言对于对于DFADFA，给定串，给定串w=xw=x1 1x x2 2xxn n；初始时，初始时，DFADFA处于开始状态处于开始状态q q0 0 从左到右逐个字符地扫描串从左到右逐个字符地扫描串w w第30页，共173页
11、，编辑于2022年，星期六 在在(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页，编辑于2022年，星期六当将串当将串w w扫描结束扫描结束后，后，若若DFADFA处于某一个处于某一个接收状态接收状态，则有限状态自动机能够则有限状态自动机能够接收接收串串w w第32页，共173页，编辑于2022年，星期六对于对于可接收串可接收串DFADFA从从开开始始状状态态开开始始，在在扫扫描描串串的的过过程程中，中，
12、状态逐个地变化状态逐个地变化,串扫描结束后，串扫描结束后，到达到达某个某个接收状态接收状态。第33页，共173页，编辑于2022年，星期六对于对于不可接收串不可接收串DFADFA从从开开始始状状态态开开始始，在在扫扫描描串串的的过过程中，程中，状态逐个地变化状态逐个地变化,串扫描结束后，串扫描结束后，处于处于非接收状态非接收状态。第34页，共173页，编辑于2022年，星期六对于字母表对于字母表上的上的DFADFA 能识别的所有串的集合，就是能识别的所有串的集合，就是DFADFA能接收的语言能接收的语言:L(DFA)L(DFA)也称为有限状态语言（也称为有限状态语言（FSLFSL）第35页，共
13、173页，编辑于2022年，星期六思考思考如何如何形式化形式化定义定义L(DFA)L(DFA)?第36页，共173页，编辑于2022年，星期六定义3-4 扩展的状态转换函数给给定定DFADFA，扩扩展展的的状状态态转转换换函函数数*：QQ*QQ 即即 *(q,(q,w w)=q)=q即即DFADFA在在一一个个状状态态q q时时，扫扫描描串串w w后后到到达唯一达唯一确定确定的状态的状态qq第37页，共173页，编辑于2022年，星期六递归扩展的状态转换函数 *(q q,)=,)=q q；*(q,a)=(q,a)(q,a)=(q,a)其中其中a a；第38页，共173页，编辑于2022年，星期
14、六对于串对于串w=w=a a（+）*（q q，w w）=*(q(q，a a）=(*(q,(q,),),a a)第39页，共173页，编辑于2022年，星期六或者或者 对于串对于串w=w=a a *(q(q，w w)=*(q(q，a a)=*(q(q，a a),),)第40页，共173页，编辑于2022年，星期六定义定义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页，编辑于2022年，星期六思考思考如何描述如何描述 在某个在某个时刻时刻，
15、DFA所处的情况？所处的情况？第42页，共173页，编辑于2022年，星期六定义定义3-7 DFA3-7 DFA的瞬时描述（格局）的瞬时描述（格局）格局是一个二元式：格局是一个二元式：q qy y q q是是DFADFA当前状态当前状态 y y是输入带上还没有被扫描到的串是输入带上还没有被扫描到的串 读头将扫描读头将扫描y y串的第串的第1 1个符号个符号第43页，共173页，编辑于2022年，星期六 在在扫扫描描串串的的过过程程中中，格格局局在在发发生生转转换换(改变改变)格格局局的的(一一次次)转转换换的的原原因因是是由由于于函数函数的的(一次一次)作用作用第44页，共173页，编辑于20
16、22年，星期六 如果当前格局为：如果当前格局为：q qa ar r 有有函数：函数：(q(q，a)=qa)=q 则下一格局为：则下一格局为：qrqr ；格局的转换可以记为：格局的转换可以记为：qar qar=qr qr；第45页，共173页，编辑于2022年，星期六DFA的特殊格局初始格局为：初始格局为：q q0 0w w接收格局为：接收格局为：q qf f其中，其中，q qf f是某个接收状态是某个接收状态 第46页，共173页，编辑于2022年，星期六使用使用=*代表格局的代表格局的任意次任意次转换转换使用使用=+代表格局的代表格局的多次多次转换转换第47页，共173页，编辑于2022年，
17、星期六可以使用可以使用格局的转换格局的转换方式定义方式定义FSLFSL第48页，共173页，编辑于2022年，星期六DFADFA接收的语言接收的语言 L(DFA)=L(DFA)=w|q w|q0 0w=w=*q qf f；ww*且且q qf fFF第49页，共173页，编辑于2022年，星期六定义3-8 DFA停机DFA将输入串扫描结束时将输入串扫描结束时 (自动自动)停机停机第50页，共173页，编辑于2022年，星期六注意1：DFA将输入串扫描结束停机时，将输入串扫描结束停机时，如果如果DFA处于某一个处于某一个接收状态接收状态，则则表示接收整个输入串；表示接收整个输入串；反之，则表示反之
18、，则表示不接收不接收整个输入串整个输入串;第51页，共173页，编辑于2022年，星期六注意2：对于状态对于状态q,如果如果不能识别不能识别字母字母a 则将状态转换到一个特殊的状态：则将状态转换到一个特殊的状态：陷阱状态陷阱状态qt 即即 (q，a)=qt第52页，共173页，编辑于2022年，星期六 陷阱陷阱状态状态qt不能够改变为其他状态不能够改变为其他状态 即即 对于对于a (qt，a)=qt第53页，共173页，编辑于2022年，星期六构造构造DFA，分别接收语言，分别接收语言0，1*0，1+0 =0=0 01第54页，共173页，编辑于2022年，星期六定理3-1 每个每个FSLFS
19、L都是一个都是一个右线性语言右线性语言分析：分析：已知已知 接收接收FSL的的DFA 构造构造 右线性文法右线性文法产生该产生该FSL第55页，共173页，编辑于2022年，星期六证明思路证明思路状态转换函数和产生式的状态转换函数和产生式的等价等价作用作用 (q,a)=q AaB 接收接收a 产生产生a 状态状态变化变化 非终结符号非终结符号变化变化结论结论:DFA:DFA状态状态等价于文法等价于文法非终结符非终结符第56页，共173页，编辑于2022年，星期六思考思考 DFA的接收状态的作用的接收状态的作用第57页，共173页，编辑于2022年，星期六证明假设假设L L是字母表是字母表上的上
20、的FSLFSL，则，则 L=L(DFA)L=L(DFA)第58页，共173页，编辑于2022年，星期六 DFA=DFA=（Q Q，q q0 0，F F）构造构造右线性右线性文法文法G=(,G=(,Q,Q,q q0 0，P P）其中其中P P为：为：第59页，共173页，编辑于2022年，星期六 qaqqaq|(q|(q，a)=qa)=q U U qqa a|(q|(q，a)Fa)F 特别，若特别，若q q0 0是接收状态，则是接收状态，则 q q0 0第60页，共173页，编辑于2022年，星期六对于串w=x1x2xn：DFA：则文法有则文法有(q0,x1)=q1 q0 x1q1；(q1,x2
21、)=q2 q1x2q2；(qn-2,xn-1)=qn-1 qn-2xn-1qn-1(qn-1,xn)=qn qn-1xnqn 或或 qn-1xn 第61页，共173页，编辑于2022年，星期六所以 DFA 文法文法*(q，)=q q=*q*(q0，w)F q0=*w第62页，共173页，编辑于2022年，星期六例例3-2 DFA与文法的转换与文法的转换FSLFSL=(0,1)1=(0,1)1*00*接收该语言的接收该语言的DFADFA为：为：第63页，共173页，编辑于2022年，星期六q11001q0第64页，共173页，编辑于2022年，星期六构造构造正则正则文法产生该语言：文法产生该语言
22、：q00q1|1q1|q10q0|1q1|0第65页，共173页，编辑于2022年，星期六定理定理3-2FSL对对补补运算封闭运算封闭第66页，共173页，编辑于2022年，星期六证明：设设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页，编辑于2022年，星期六构造构造 DFA DFA2 2=（Q Q，q q0 0，Q Q）DFADFA2 2接收的语言是接收的语言是 L L1 1的对应的全集的对应的全集,即即*第68页，共173页，编辑于2022年，星期六构造构造 DFA DF
23、A3 3=(Q=(Q，q q0 0，Q-FQ-F)DFA DFA3 3接收的语言是接收的语言是L L1 1的的补补 L L3 3=L(DFA=L(DFA3 3)也是也是FSLFSL语言。语言。第69页，共173页，编辑于2022年，星期六注意此时的此时的DFADFA1 1的的函数的个数为函数的个数为|Q|Q|*|第70页，共173页，编辑于2022年，星期六基本的等价替换基本的等价替换l对于状态转换图，有基本的等价替换对于状态转换图，有基本的等价替换l变换为00,11第71页，共173页，编辑于2022年，星期六3.3 DFA3.3 DFA识别语言的例子识别语言的例子 构造构造DFA，接收语言
24、接收语言 L=ab 第72页，共173页，编辑于2022年，星期六基本结构（接收基本句子）基本结构（接收基本句子）q1abq0q2第73页，共173页，编辑于2022年，星期六增加增加陷阱状态陷阱状态后的后的DFADFAq1abq0qtbaa,ba,bq2第74页，共173页，编辑于2022年，星期六思考思考1 1 如如果果将将该该DFADFA的的所所有有状状态态都都设设置置为为接收状态接收状态(包括陷阱状态包括陷阱状态)，接收的语言是接收的语言是？第75页，共173页，编辑于2022年，星期六思考思考2 2 如如果果将将该该自自动动机机的的接接收收状状态态和和非非接接收收状态对调状态对调 接
25、收的语言是接收的语言是？第76页，共173页，编辑于2022年，星期六例3-4构造DFA识别语言识别语言L=L=x000yx000y|x,y0,1|x,y0,1*第77页，共173页，编辑于2022年，星期六分析 该语言的特点是该语言的特点是 语语言言中中的的每每个个串串都都包包含含连连续续的的3 3个个0 0（即每个串都包含子串（即每个串都包含子串000000）第78页，共173页，编辑于2022年，星期六 因因此此，对对于于任任何何输输入入串串，有有限限状状态态自自动动机机的的任任务务就就是是要要检检查查该该输输入入串串中是否存在子串中是否存在子串000000，一一旦旦发发现现输输入入串串
26、包包含含有有000000，则则表表示示整个输入串整个输入串是是句子句子。第79页，共173页，编辑于2022年，星期六因此，在确认输入串包含因此，在确认输入串包含000000后，后，就就可可以以逐逐一一地地读读入入000000后后面面的的全全部部字符，并接收该输入串。字符，并接收该输入串。第80页，共173页，编辑于2022年，星期六思考思考问题的关键是问题的关键是？如何如何发现发现子串子串000000。第81页，共173页，编辑于2022年，星期六由由于于字字符符是是逐逐一一读读入入的的，当当从从输输入入串中读入一个串中读入一个0 0时，时，它它有可能有可能是是000000的的第第1 1个个
27、0 0，需要需要记住记住已经出现过一个已经出现过一个0 0；第82页，共173页，编辑于2022年，星期六如果紧接着读入的是字符如果紧接着读入的是字符1 1，则刚读入的则刚读入的0 0就不是就不是000000的第的第1 1个个0 0需要需要重新寻找重新寻找000000子串的第子串的第1 1个个0 0；第83页，共173页，编辑于2022年，星期六如如果果紧紧接接着着读读入入的的还还是是0 0，它它有有可可能能是是000000的的第第2 2个个0 0，也需要也需要记住记住这个这个0 0，继续读入字符，若是继续读入字符，若是0 0，则，则发现发现000000否则，需要否则，需要重新重新寻找寻找00
28、0000。第84页，共173页，编辑于2022年，星期六初始状态：初始状态：q q0 0接收接收0 0，到达状态，到达状态q q1 1接收接收00,00,到达状态到达状态q q2 2接收接收000,000,到达状态到达状态q q3 3第85页，共173页，编辑于2022年，星期六因此，因此，基本的基本的状态转移函数为：状态转移函数为：(q(q0 0，0)=q0)=q1 1 (q (q1 1，0)=q0)=q2 2 (q (q2 2，0)=q0)=q3 3用于接收基本句子用于接收基本句子000000第86页，共173页，编辑于2022年，星期六接收接收000000的状态图的状态图q0000q1q
29、2q3第87页，共173页，编辑于2022年，星期六其他状态转移函数为：其他状态转移函数为：(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页，编辑于2022年，星期六状态转移图状态转移图q00111000,1q1q2q3第89页，共173页，编辑于2022年，星期六思考思考如果需要接收
30、语言如果需要接收语言 L 如何修改有限状态自动机如何修改有限状态自动机?思路：思路：考虑考虑开始状态开始状态的作用的作用第90页，共173页，编辑于2022年，星期六思考思考:如果如果 DFA的的开始状态开始状态只负责识别输入串只负责识别输入串的第一个字母；的第一个字母；文法的文法的开始符号开始符号只负责串的推导的只负责串的推导的开始；开始；优点是？优点是？第91页，共173页，编辑于2022年，星期六状态图为状态图为10qs01000,1q1q2q3q011第92页，共173页，编辑于2022年，星期六例3-5构造DFA 识别语言识别语言 L=L=x x001001y y|x|x，y0y0，
31、11*第93页，共173页，编辑于2022年，星期六分析：对于任何输入串，对于任何输入串，DFADFA的任务就是的任务就是要检查该输入串中是否存在要检查该输入串中是否存在001001 第94页，共173页，编辑于2022年，星期六初始状态：初始状态：q q0 0q q1 1 已接收已接收0 0q q2 2 已接收已接收00 00 q q3 3 已接收已接收001 001 第95页，共173页，编辑于2022年，星期六q2q1q0状态转移图状态转移图01q31010,10第96页，共173页，编辑于2022年，星期六例3-6 构造DFA识别语言识别语言L=L=x x000000|x0|x0，11
32、*第97页，共173页，编辑于2022年，星期六q2q3q1q001110001第98页，共173页，编辑于2022年，星期六例3-7构造DFA识别语言识别语言L=L=x x000000 x x001001其中，其中，x0 x0，11*第99页，共173页，编辑于2022年，星期六q2q1q001q310001q4101第100页，共173页，编辑于2022年，星期六例3-8构造DFA识别语言识别语言L=L=0 02k+3m2k+3m|m,k=0|m,k=0 第101页，共173页，编辑于2022年，星期六实际上：实际上：2k+3m2k+3m可以表示任意的可以表示任意的非负整数非负整数(除除1
33、 1外外)该语言为该语言为0*-0 第102页，共173页，编辑于2022年，星期六状态转移图状态转移图000q1q2q0第103页，共173页，编辑于2022年，星期六思考：构造DFA识别语言识别语言L=0L=02k+3m2k+3m|m,k0m,k0 考查题考查题 1第104页，共173页，编辑于2022年，星期六例3-9构造DFA 识别识别00，11上的语言，该语言的上的语言，该语言的 每个句子以每个句子以0 0开头，以开头，以1 1结尾。结尾。第105页，共173页，编辑于2022年，星期六状态转移图状态转移图010q1q210qt0,11q0第106页，共173页，编辑于2022年，星
34、期六例3-10 构造DFA识别识别00，11上的语言，该语言的每个上的语言，该语言的每个字符串字符串 不包含不包含0000子串子串(语言允许语言允许)第107页，共173页，编辑于2022年，星期六000,1qtq1q0q21011第108页，共173页，编辑于2022年，星期六或或000,1qtq1q011第109页，共173页，编辑于2022年，星期六构造DFA识别识别00，11上的语言，上的语言，该语言的每个字符串不包含该语言的每个字符串不包含0000（语言不允许语言不允许 ）第110页，共173页，编辑于2022年，星期六例3-11构造DFA识别识别00，1 1，22上的语言，上的语言
35、，该语言的每个字符串代表的数字能整该语言的每个字符串代表的数字能整除除3 3。第111页，共173页，编辑于2022年，星期六分析 如如果果一一个个十十进进制制整整数数的的所所有有位位的的数数字的和字的和能够整除能够整除3 3，那么，那么，这个十进制整数就能够整除这个十进制整数就能够整除3 3；第112页，共173页，编辑于2022年，星期六一一个个十十进进制制整整数数除除以以3 3，余余数数只只能能是是1 1、2 2和和0 0；第113页，共173页，编辑于2022年，星期六 将将整整数数当当作作一一个个字字符符串串，从从左左到到右右逐一地读入；逐一地读入；使使用用3 3个个状状态态分分别别
36、代代表表已已读读入入的的数数字的字的和和除以除以3 3的的余数情况余数情况：(即读入的整数对即读入的整数对3 3的余数情况）的余数情况）第114页，共173页，编辑于2022年，星期六q q0 0：已已读入的整数除以读入的整数除以3 3，余数为余数为0 0q q1 1：已已读入的整数除以读入的整数除以3 3，余数为余数为1 1q q2 2：已已读入的整数除以读入的整数除以3 3，余数为余数为2 2第115页，共173页，编辑于2022年，星期六思考思考 已知已知qi(i=0,1,2)，n=0,1,2，应该如何确定应该如何确定 j？qiqjn第116页，共173页，编辑于2022年，星期六 扫描
37、子串扫描子串w w后后,处于某个状态处于某个状态q qi i，读入当前数字读入当前数字,状态转换情况为状态转换情况为第117页，共173页，编辑于2022年，星期六q0l在在此此状状态态读读入入0 0，引引导导DFADFA到到达达下下一一状态的输入串为状态的输入串为w0w0,lw0w0的的各各位位数数字字和和除除以以3 3，余余数数为为0 0。所所以以，DFADFA在在q q0 0状状态态读读入入0 0，应应该该继继续保持续保持q q0 0状态；状态；第118页，共173页，编辑于2022年，星期六q0l在在此此状状态态读读入入1 1，引引导导DFADFA到到达达下下一一状状态态的的输输入入串
38、串为为w1w1，w1w1的的各各位位数数字字和除以和除以3 3，余数为余数为1 1。l所所以以，DFADFA在在q q0 0状状态态读读入入1 1，应应该该到到达达q q1 1状态；状态；第119页，共173页，编辑于2022年，星期六q0l在此状态读入在此状态读入2 2，引导，引导DFADFA到达下一到达下一状态的输入串为状态的输入串为w2w2，w2w2的各位数字的各位数字和除以和除以3 3，余数为余数为2 2。l所以，所以，DFADFA在在q q0 0状态读入状态读入2 2，应该，应该到达到达q q2 2状态；状态；l第120页，共173页，编辑于2022年，星期六第121页，共173页，
39、编辑于2022年，星期六存在的问题 接收的串包括以接收的串包括以0开始开始的数字串；的数字串；还能够接收还能够接收空串空串第122页，共173页，编辑于2022年，星期六思考如何进行改进，使得如何进行改进，使得 接收的串不能以接收的串不能以0开始，开始，不能接收不能接收空串空串。第123页，共173页，编辑于2022年，星期六定义3-9 set集合对于状态对于状态q，能将，能将DFA从从q0转换到转换到q状状态的所有字符串的集合为：态的所有字符串的集合为：set(q)set(q)=w|w=w|w*,*(q(q0 0,w)=q,w)=q 第124页，共173页，编辑于2022年，星期六则则有限状
40、态自动机有限状态自动机DFADFA接收的接收的语言可语言可以定义为：以定义为：L(DFA)=set(q)其中：其中：q qFF第125页，共173页，编辑于2022年，星期六按状态进行划分按状态进行划分对于对于DFADFA，可以定义关系可以定义关系R R 若若 x,yx,y*，qQ qQ 则则 xRy xRy 当且仅当当且仅当 xset(q),yset(q)xset(q),yset(q)第126页，共173页，编辑于2022年，星期六 该该关关系系是是集集合合*上上的的一一个个等等价价关关系系，利用该关系，利用该关系，可可以以将将*划划分分为为不不多多于于|Q|Q|个个的的等等价类价类。第12
41、7页，共173页，编辑于2022年，星期六 DFADFA可可以以按按照照语语言言的的特特点点给给出出字字母母表表*的的一一个个划划分分，这这种种划划分分相相当当于于*上的一个等价分类。上的一个等价分类。DFA DFA每个每个状态状态对应着一个对应着一个等价类等价类第128页，共173页，编辑于2022年，星期六 利用一个利用一个状态状态去表示一个去表示一个等价类等价类是构造是构造DFADFA的一条的一条有效思路有效思路。第129页，共173页，编辑于2022年，星期六例3-12构造DFA,识别 0,1,2,4,5,6,7,8,9 0,1,2,4,5,6,7,8,9上的语言，上的语言，该语言的每
42、个字符串代表的数字能该语言的每个字符串代表的数字能整除整除3 3。第130页，共173页，编辑于2022年，星期六 仍仍然然只只使使用用3 3个个状状态态分分别别代代表表已已经经读读入入的的整整数数字字的的和和除除以以3 3的的不不同同的的余余数的情况：数的情况：第131页，共173页，编辑于2022年，星期六状态与对应的等价类状态与对应的等价类q q0 0：余数为余数为0 0的输入串的等价类的输入串的等价类q q1 1：余数为余数为1 1的输入串的等价类的输入串的等价类q q2 2：余数为余数为2 2的输入串的等价类的输入串的等价类第132页，共173页，编辑于2022年，星期六第133页，
43、共173页，编辑于2022年，星期六例3-13构造DFA,识别00，11上的语言，该语言的每个字符上的语言，该语言的每个字符串挡成串挡成二进制数二进制数时，时，代表的数字能代表的数字能整除整除3 3。第134页，共173页，编辑于2022年，星期六 DFA DFA的每个状态对应一个等价类的每个状态对应一个等价类 利用一个状态去表示一个等价类利用一个状态去表示一个等价类 除以除以3 3的的余数只能为余数只能为0 0、1 1和和2 2第135页，共173页，编辑于2022年，星期六q q0 0：余数为余数为0 0的输入串的等价类；的输入串的等价类；q q1 1：余数为余数为1 1的输入串的等价类；
44、的输入串的等价类；q q2 2：余数为余数为2 2的输入串的等价类；的输入串的等价类；第136页，共173页，编辑于2022年，星期六不能接收空串，所以，不能接收空串，所以，还需要一个开始状态还需要一个开始状态q qS S第137页，共173页，编辑于2022年，星期六设设w是当前读入的输入串；是当前读入的输入串；qS：在开始状态：在开始状态读入读入0时，时，w=0，进入状态，进入状态q0；读入读入1时，时，w=1，进入状态，进入状态q1；第138页，共173页，编辑于2022年，星期六q0 能引导能引导DFA到达此状态的到达此状态的w除以除以3余余数为数为0，因此，因此 (w)10=3n+0
45、第139页，共173页，编辑于2022年，星期六q0 在此状态读入在此状态读入0，引导，引导DFA到达下一到达下一状态的输入串为状态的输入串为w0，则，则 (w0)10=2(3n+0)+0=32n+0 表明表明w0也属于也属于q0对应的等价类。所对应的等价类。所以，以，DFA在在q0状态读入状态读入0，应该继续保，应该继续保持持q0状态；状态；第140页，共173页，编辑于2022年，星期六q0 在此状态读入在此状态读入1，引导，引导DFA到达下一到达下一状态的输入串为状态的输入串为w1，则，则 (w1)10=2(3n+0)+1=32n+1 表明表明w1属于属于q1对应的等价类。所以，对应的等
46、价类。所以，DFA在在q0状态读入状态读入1，应该到达，应该到达q1状态；状态；第141页，共173页，编辑于2022年，星期六 q1 能引导能引导DFA到达此状态的到达此状态的w除以除以3余数为余数为1，因此，因此 (w)10=3n+1第142页，共173页，编辑于2022年，星期六q1 在此状态读入在此状态读入0，引导，引导DFA到达下一到达下一状态的输入串为状态的输入串为w0，则，则 (w0)10=2(3n+1)+0=32n+2 表明表明w0属于属于q2对应的等价类。所对应的等价类。所以，以，DFA在在q1状态读入状态读入0，应该到达，应该到达q2状态；状态；第143页，共173页，编辑
47、于2022年，星期六q1 在此状态读入在此状态读入1，引导，引导DFA到达下一到达下一状态的输入串为状态的输入串为w1，则，则 (w1)10=2(3n+1)+1=32n+3 表明表明w1属于属于q0对应的等价类。所以，对应的等价类。所以，DFA在在q1状态读入状态读入1，应该到达，应该到达q0状态；状态；第144页，共173页，编辑于2022年，星期六q2 能引导能引导DFA到达此状态的到达此状态的w除以除以3余余数为数为2，因此，因此，(w)10=3n+2第145页，共173页，编辑于2022年，星期六q2 在此状态读入在此状态读入0，引导，引导DFA到达下一到达下一状态的输入串为状态的输入
48、串为w0，则，则 (w0)10=2(3n+2)+0=32n+4 表明表明w0属于属于q1对应的等价类。所以，对应的等价类。所以，DFA在在q2状态读入状态读入0，应该到达，应该到达q1状态；状态；第146页，共173页，编辑于2022年，星期六q2 在此状态读入在此状态读入1，引导自动机到达，引导自动机到达下一状态的输入串为下一状态的输入串为w1，则，则(w1)10=2(3n+2)+1=32n+5 表明表明w1属于属于q2对应的等价类。所以，对应的等价类。所以，自动机在自动机在q2状态读入状态读入1，继续保持，继续保持q2状态；状态；第147页，共173页，编辑于2022年，星期六状态图状态图
49、第148页，共173页，编辑于2022年，星期六例3-14构造DFA，识别 0，1上的语言，该语言的每个字上的语言，该语言的每个字符串为符串为二进制数二进制数时，时，代表的数字能被代表的数字能被5整除。整除。第149页，共173页，编辑于2022年，星期六分析：分析：l对对5的余数只能为的余数只能为0、1、2、3和和4l使用使用5个状态个状态分别代表已经读入的数字除以分别代表已经读入的数字除以5的的不同的余数的等价类：不同的余数的等价类：lqi：已经读入的数除以：已经读入的数除以5，余数为，余数为i的输入串的的输入串的等价类；等价类；l其中其中 i=0,1,2,3,4l不能接收空串，需要一个开
50、始状态不能接收空串，需要一个开始状态qS第150页，共173页，编辑于2022年，星期六第151页，共173页，编辑于2022年，星期六例3-15构造DFA，识别 1,2,3上的语言，该语言的每个上的语言，该语言的每个字符串挡成字符串挡成十进制数十进制数时，时，代表的数字能被代表的数字能被4整除。整除。第152页，共173页，编辑于2022年，星期六第153页，共173页，编辑于2022年，星期六思考：思考：构造DFA，识别 0 0，1,21,2，3 3，4 4，5 5，6 6，7 7，8 8，99上上的语言，该语言的每个字符串挡成的语言，该语言的每个字符串挡成十进制十进制数时，数时，代表的数