有限自动机理论CH3PART2.ppt

.4 .4 不确定的有限状态自动机不确定的有限状态自动机每个每个FSLFSL都是都是右线性语言右线性语言(定理定理3-13-1)问题问题 每个每个右线性语言右线性语言是不是一个是不是一个FSLFSL？例例接收语言接收语言 aaaa，abab 的的FAFA省略省略陷阱状陷阱状态态q1abq0q2aaq3 该自动机识别的语言该自动机识别的语言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的状态转换函数的状态转换函数即即(q，a)2QNFA在状态在状态q，扫描字母，扫描字母a后到达后到达可能可能的的下一下一状态集合状态集合。NFA与DFANFA有有一一个个可可能能的的开开始始状状态态集集合合和可能的下一和可能的下一状态集合状态集合其余的同其余的同DFA。NFA与与DFA的的重要重要区别区别在于在于转移函数转移函数的不同。的不同。(q，x)对应对应的是的是状态的一个子集状态的一个子集FA处于状态处于状态qDFA对每个对每个字母字母只有一个状态的转移。只有一个状态的转移。NFA对对某某个个字母字母可以有可以有多个状态转移多个状态转移；NFA接接收收该该字字母母时时,从从多多个个状状态态转转移移中中非确定非确定地地选择选择任意任意一个一个。具体地具体地对于对于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时时，NFA的的状状态态发发生转换，可能会有多种生转换，可能会有多种情况：情况：可能在可能在接收状态接收状态时终止；时终止；可能在可能在非接收状态非接收状态时终止；时终止；也可能在也可能在中途停止中途停止。若若至至少少存存在在一一条条路路径径可可以以使使NFA在扫描串在扫描串w后到达接收状态后到达接收状态则串则串w能被能被NFA所识别所识别。对对于于字字母母表表上上的的NFA，它它能能识识别别的的所所有有串串的的集集合合，称称为为NFA能能识识别的语言。别的语言。记为记为L(NFA)问题问题l如何形式化定义如何形式化定义L(NFA)?定义3-11NFA扩展状态转换函数l给定给定NFA，扩展的状态转换函数，扩展的状态转换函数*：2Q*2Q为为*(p，w)=Q即即NFA在在状状态态集集合合p时时，扫扫描描串串w后到达可能的的状态集合后到达可能的的状态集合Q。NFA扩展状态转换函数若若p=q1，q2，qn；*（p，）=pa*(p，a)=(q，a)|qp=(q1,a),(q2,a),(qn,a)对于串对于串ww=a*(p，w)=*(p，a)=(q，a)|q*(p，)或或w=a*(p，w)=*(p，a)=*(q,)|q*(p，a)L(NFA)表示被表示被NFA所接收的语言所接收的语言L(NFA)=w|w*且且*(Q0，w)Fl它表示所有串它表示所有串w的集合的集合在在NFA的的状状态态图图中中，至至少少存存在在一一条路径条路径以以w为为标标记记，能能使使NFA从从某某个个开开始状态到达某个接收状态。始状态到达某个接收状态。3.4.2NFA的的确定化确定化DFA可以转换为可以转换为NFANFA可以转换为可以转换为DFA(确定化确定化)A的的充分条件充分条件为为BA的的必要条件必要条件为为BA当且仅当当且仅当B即即A的的充要条件充要条件为为BB=AA=B定理3-3l*的一个子集的一个子集L是一个是一个FSL，充要条件为充要条件为存在存在NFA，使得，使得L(NFA)=L。证明：证明：=必要性必要性l若若L是是FSL，则有则有L=L(DFA）DFA=(Q，q0，F)构造构造NFA=(Q，1，q0，F)1(q，a)=(q，a)即把即把DFA的一个状态的一个状态当作当作NFA的一个状态集合的一个状态集合则则L=L(DFA)=L(NFA)证明证明:00 NFANFA状态转移图状态转移图q0010122q1q2q3或或q0010122q1q2q3例3-27构造构造NFANFA，识别，识别 0 0，11上的语言上的语言 L=L=0 0n n1 1m m2 2k k|n,m,k=n,m,k=0 0 010122q3q0q1q2212或或多个开始状态的多个开始状态的NFA1022q3q1q2123.5带带动作的有限状态自动机动作的有限状态自动机 对于对于FAFA（DFADFA、NFANFA），有），有 (q(q，)=q)=q *(q(q，)=q)=q *(P(P，)=P)=P 表表示示FAFA不不读读入入任任何何字字母母(即即只只扫扫描空串时描空串时)，FAFA的的状状态态不不发发生生改改变变，并并且且读读头头不不进进行行移移动动，仍仍然然指指向向当当前前非非空字符。空字符。若若允允许许FAFA在在不不读读入入任任何何字字符符时时,FA,FA的的状态可以发生改变状态可以发生改变，则则FAFA为为带有带有动作动作的的FAFA定义定义3-14带带动作的有限状态自动机动作的有限状态自动机带有带有动作的动作的FA是一个五元式是一个五元式,-FA=(Q，Q0，F)Q，Q0，F的含义同的含义同NFA:Q 2Q(q，a)2Q(q,)2Q即即具体具体(q，a)=表表示示自自动动机机在在读读入入字字母母a后后，自自动动机停机。机停机。(q,)=q表表示示自自动动机机在在状状态态q时时，不不读读入入任任何字母，自动机状态不变何字母，自动机状态不变并且读头不移动；并且读头不移动；(q，a)=p1，p2，p3，pm表表示示自自动动机机在在读读入入字字母母a后后，自自动动机机的的状状态态可可以以选选择择地地改改变变为为p1，p2，p3，或者，或者pm并将读头向右移动一个单元；并将读头向右移动一个单元；(q,)=q1，q2，q3，qn表表示示自自动动机机在在状状态态q时时，不不读读入入任任何何字字母母，自自动动机机的的状状态态可可以以选选择择地地改变为改变为q1，q2，q3，或，或qn并且读头不移动；并且读头不移动；注意注意带有带有动作的动作的FA一定一定是是NFA。一般，记为一般，记为-NFA。例例3-28使用使用-NFA接收语言接收语言L=0*1*2*即即L=0n1m2k|n,m,k=0状态图状态图0*1*2*q0q1q2 201 对应的对应的5个个函数为：函数为：(q0，0)=q0(q0，)=q1(q1，1)=q1(q1，)=q2(q2，2)=q2定义3-15对于对于-NFA，qQ从从q开开始始，扫扫描描1个个或或多多个个后后能够到达的状态集记为能够到达的状态集记为-CLOSURE(q)。-CLOSURE(q)=p|从从q到到p有标记有标记全是全是的有的有向路向路对于对于-NFA，qQ-CLOSURE(q)是是由由递递归归规规则则确定确定的状态集：的状态集：规则(1)q-CLOSURE(q)即即任任意意状状态态q接接收收空空串串，至至少少都能都能保持状态保持状态q不变；不变；规则规则(2)如果如果p-CLOSURE(q)则则(p,)-CLOSURE(q)(3)重重复复(2)，直直到到-CLOSURE(q)中的状态不再增加为止。中的状态不再增加为止。注意-CLOSURE(q)与与(q,)不同不同进一步对于对于状态集合状态集合P P，定义，定义-CLOSURE(P)=qP-CLOSURE（q）定义定义3-16 3-16 扩展的状态转换函数扩展的状态转换函数-NFA 扩展状态转换函数扩展状态转换函数 *：2 2Q Q *22Q Q为为 *（P P，w w）=Q=Q 即即自自动动机机在在状状态态集集合合P P时时，扫扫描描串串w w后到达的状态集合后到达的状态集合QQ。空串空串*(P,)=-CLOSURE(P)*(q,)=-CLOSURE(q)*(q,)=?单个字母单个字母*(P，a)=*(q，a)*(q，a)=*(q，a)=-CLOSURE(P)=-CLOSURE(p,a)qPp*(q,)对于串对于串wa*(P,wa)=*(*(P,w),a)或或*(P,aw)=*(*(P,a),w)对于-CLOSURE(q0)=-CLOSURE(q1)=-CLOSURE(q2)=q0q1q2 201 q0q1，q2q2,q1,q2对于*(q0,)=-CLOSURE(q0)=q0，q1，q2q0q1q2 201*(q0,0)=*(q0,0)=-CLOSURE(p,0)p*(q0,)=-CLOSURE(q0,0)(q1,0)(q2,0)=-CLOSURE(q0)=q0，q1，q2q0q1q2 201*（q0,01）=*(*(q0,0),1)=*(q0,q1,q2,1)=-CLOSURE(q0,1)(q1,1)(q2,1)=q1,q2q0q1q2 201 注意*(q(q，)与与(q(q，)不同不同定理3-5 如果语言如果语言L L被被-NFA接收，则接收，则 该语言该语言L L也能够被一个也能够被一个NFANFA接收接收证明证明 ：假设语言假设语言L L被一个被一个-NFA接收接收,-NFA=(Q=(Q，Q Q0 0，F)F)1)1)构造构造 NFA1=(Q，1，Q0，F1)其中其中:对于对于a1(q，a)=*（q，a）F1=Fq0若若F-CLOSURE(q0)F1=F若若F-CLOSURE(q0)=2 2）证明对于证明对于ww+,有有 1 1(q(q0 0，w)=w)=*（qq0 0,w,w）过程自学过程自学 结论 如如果果语语言言L L被被-NFA接接收收，则则语言语言L L也能够被一个也能够被一个NFANFA接收接收例3-29将将-NFA改造为等价的改造为等价的NFA。q0q1q2 201 q1q0q22010,11,20,1,2例3-30构造-NFA,识别0，1上的语言上的语言L=0k|k=0，k能够被能够被2或或3整除整除即即L=02n或或03m|n,m=0q0q1q3q2q4q500000思考L=02n+3m|n,m0请请验证验证q0q5q10q20q30q40000思考：-NFA-NFA转换为转换为NFANFA能否能否 先将先将-NFA-NFA转换为转换为“右线性右线性”文法，再转换为文法，再转换为NFANFA？引进单产生式引进单产生式A AB B3.6有限状态自动机的一些有限状态自动机的一些变形变形有限状态自动机存在变形。有限状态自动机存在变形。3.6.1双向的有限状态自动机双向的有限状态自动机在处理输入串的过程中，在处理输入串的过程中，双向的有限状态自动机的双向的有限状态自动机的读头读头可以可以向右向右移动一个单元；移动一个单元；也可以也可以向左向左移动一个单元；移动一个单元；也可以也可以不移动不移动。定义3-18确确定定的的双双向向的的有有限限状状态态自自动动机机(2DFA)是一个五元式：是一个五元式：2DFA=（Q，q0，F）其中，其中，Q,q0，F的含义同的含义同DFA：状态转换函数；状态转换函数；QQL，R，N对于对于qQ，a(q，a)=p，D2DFA在状态在状态q读入字母读入字母a自动机状态将变为自动机状态将变为p状态状态D=L读头向左移动一个单元读头向左移动一个单元D=R读头向左移动一个单元读头向左移动一个单元D=N读头位置不变；读头位置不变；2DFA格局格局描述同描述同DFA2DFA=（Q，q0，F）接接收的语言为收的语言为L(2DFA)L(2DFA)=w|q0w=*q，qF定理3-62DFA与与DFA等价等价。证明：证明：略。略。可可以以定定义义不不确确定定的的双双向向的的有有限限状态自动机状态自动机。定义3-20不不确确定定双双向向有有限限状状态态自自动动机机2NFA是一个五元式：是一个五元式：2NFA=(Q，Q0，F)其中其中Q，Q0，F的含义同的含义同NFA：状态转换函数；：状态转换函数；：Q2QL，R，N对于对于qQ，a,D1，D2，DmL,R,N，(q,a)=(p1,D1),(p2,D2),(pm,Dm)2NFA在状态在状态q读入字母读入字母a可以将状态变为可以将状态变为pi按照按照Di实现对读头的移动实现对读头的移动定理3-72NFA与与NFA等价。等价。证明：证明：略。略。3.6.2带输出的有限状态自动机带输出的有限状态自动机FA，对于某个输入串，对于某个输入串w得到的结论是得到的结论是:是否接收该串是否接收该串；或或FA输出输出“是是”或或“否否”。存在许多有穷状态系统存在许多有穷状态系统对于不同的输入信号，对于不同的输入信号，除系统内部的状态变化之外，除系统内部的状态变化之外，还向还向系统外部系统外部输出各种信号输出各种信号。模型图有限状态系统有限状态系统输入序列输入序列输入序列输入序列典典型型带带输输出出的的有有穷穷自自动动机机-Moore机和机和Mealy机。机。由由于于它它们们带带有有输输出出，从从抽抽象象的的角角度度考考虑虑，就就没没有有必必要要再再设设置置接接收状态收状态（集）。（集）。定义3-21Moore机是一个机是一个六元式六元式：MooreM=(Q,q0)其中其中Q，q0，的含义同的含义同FA：输出字母表：输出字母表输出函数输出函数：Q对于对于qQ，a(q)=a表示表示Moore机处于状态机处于状态q时输出时输出aMoore机在读入输入串的过程中在读入输入串的过程中状态不断发生改变状态不断发生改变并且并且在每个状态上都有输出在每个状态上都有输出对于输入串a1a2a3an-1an设设(q0,a1)=q1(q1,a2)=q2(qn-2,an-1)=qn-1(qn-1,an)=qn则Moore机的输出序列可以表示为：机的输出序列可以表示为：(q0)(q1)(q2)(qn)如如果果输输入入串串的的长长度度为为n,则则Moore机的输出串的长度为机的输出串的长度为n+1。实际上FA只是只是Moore机的一个机的一个特例特例。若若Moore机的输出仅只有机的输出仅只有F或或T将将输输出出T的的状状态态当当作作接接收收状状态态，Moore机就是一般的机就是一般的FA。例3-31设计Moore机=0，1若若将将输输入入串串当当作作二二进进制制数数，则则在读入串的过程中，在读入串的过程中，希希望望输输出出已已经经读读过过的的（数数字字）串模串模3的余数。的余数。分析模模3的余数只能是的余数只能是0、1和和2输出字母表输出字母表=0，1，2状态状态q0、q1和和q2对应对应3种余数种余数状态上的标记表示状态上的标记表示MooreMoore机在该状态时机在该状态时的输出的输出q0q1q2012000111当输入为当输入为1010时时状态变换的序列为状态变换的序列为q0q1q2q2q1输出输出01221即当输入当输入时，输出余数时，输出余数0当输入当输入1时，输出余数时，输出余数1当输入当输入10时，输出余数时，输出余数2当输入当输入101时，输出余数时，输出余数2当输入当输入1010时，输出余数时，输出余数1定义3-22Mealy机是一个六元式：机是一个六元式：MealyM=(Q,，,q0)其中其中Q，q0，的含义同的含义同FA：输出字母表输出字母表输出函数输出函数：Q对于对于qQ，x，a(q，x)=a表表示示Moore机机在在状状态态q,读读入入字字母母x时，输出时，输出aMealy机在读入输入串的过程中，机在读入输入串的过程中，状态不断发生改变，状态不断发生改变，并且在读入某个字母时，并且在读入某个字母时，Mealy机都有输出。机都有输出。对于输入序列对于输入序列a1a2a3an-1an设设(q0,a1)=q1(q1,a2)=q2(qn-2,an-1)=qn-1(qn-1,an)=qn 则则Mealy机的输出序列表示为：机的输出序列表示为：(q0,a1)(q1,a2)(qn-1,an)若输入串的长度为若输入串的长度为nMealy机输出串的长度为机输出串的长度为nMoore机输出串的长度为机输出串的长度为n+1例3-32对于语言对于语言(0+1)*(00+11)设计输出符号为设计输出符号为y,n的的Mealy机机读过的子串是句子读过的子串是句子Mealy机输出机输出y,表示接收；表示接收；读过的输入串不是句子读过的输入串不是句子Mealy机输出机输出n,表示拒绝。表示拒绝。若若(p,a)=q(p,a)=b则则状态状态p到到q的有向边标记的有向边标记a/bMealy机输入串是输入串是01100Mealy机对应的输出为机对应的输出为nnyny输入输入0拒绝；拒绝；01拒绝；拒绝；011接收接收0110拒绝；拒绝；01100接收接收一一般般地地，Mealy机机比比一一般般的的有有限限状态自动机具有状态自动机具有更强更强的功效。的功效。根根据据Moore机机和和Mealy机机的的定定义义，可可 知知：对对 于于 输输 入入 串串 的的 序序 列列a1a2a3an-1an*，l1)Moore机处理该串时机处理该串时,每经过一每经过一个状态，就输出一个字符；个状态，就输出一个字符；输出字符和输出字符和状态状态一一对应一一对应。l2)Mealy机处理该串时机处理该串时,每一个每一个状状态移动态移动，就输出一个字符；，就输出一个字符；输出字符和输出字符和转换转换一一对应一一对应。Moore机和Mealy机等价设设Moore机：机：M1=(Q1，,1,1,q01)Mealy机：机：M2=(Q2，,2,2,q02)l对于输入串对于输入串w*，若，若T1(w)=1(q01)T2(w)称称Moore机和机和Mealy机是等价的。机是等价的。其中T1(w)和和T2(w)分别表示分别表示Moore机机M1和和Mealy机机M2关关于于输入串输入串w的输出。的输出。l给定任意的给定任意的Moore机，可以构机，可以构造出与之等价的造出与之等价的Mealy机；机；l给定任意的给定任意的Mealy机，也可以机，也可以构造出与之等价的构造出与之等价的Moore机。机。定理3-8Mo=(Q,1,q0)是是个个Moore机，机，则有一个则有一个Mealy机机Me与之等价。与之等价。证明l设设Moore机机Mo=（Q，1,q0）构造构造Mealy机机Me=（Q，2,q0）其中其中:2(q，a)=1(q，a)Me与与Mo具有相同状态和具有相同状态和函数函数对于相同的输入串序列对于相同的输入串序列Me与与Mo状态转换序列相同状态转换序列相同惟惟一一不不同同的的只只是是将将Mo的的输输出出前前移一步移一步(删除删除q0对应的输出对应的输出)。l Mo Meqpqpaba/b在在不不考考虑虑Mo第第一一个个输输出出符符号号的的情况下，情况下，Me与与Mo的的输输出出序序列列一一定定相相同同。证毕。证毕。定理3-9M1=(Q，1，1,q0)是一个是一个Mealy机，机，则有一个则有一个Moore机机M2与之等价。与之等价。证明思路：思路：只需要增加一个关于只需要增加一个关于q0的输出。的输出。定理3-10Moore机与机与Mealy机等价。机等价。证明：证明：根据根据定理定理3-8、定理、定理3-9。3.7有限状态自动机的存储技术有限状态自动机的存储技术lFA的有限状态控制器（的有限状态控制器（FSC）可以保存有限数量的信息，即保可以保存有限数量的信息，即保存多个状态。存多个状态。可以使用可以使用n元组元组表示表示一个状态一个状态而而n元组的不同的分量可以代表元组的不同的分量可以代表不同的含义。不同的含义。l最简单是使用二元组表示最简单是使用二元组表示第一个分量表示原来的状态第一个分量表示原来的状态第二个分量是需要第二个分量是需要存储存储的信息的信息一个分量实现一个分量实现控制控制一个分量实现一个分量实现存储存储l该技术也适合该技术也适合下推自动机下推自动机和和图灵机图灵机。例3-34构造 FA 识别a，b，c上语言上语言L该该语语言言的的每每个个句句子子的的第第一一个个符符号在该句子中仅仅出现号在该句子中仅仅出现一次一次。存储第一个字符存储第一个字符(start，a)=q，a(start，b)=q，b(start，c)=q，c扫描扫描(q，a，b)=q，a(q，a，c)=q，a(q，b，a)=q，b(q，b，c)=q，b(q，c，a)=q，c(q，c，b)=q，c其中其中start是开始状态是开始状态q，a、q，a和和q，c是接收状态是接收状态l有限状态自动机的基本结构和有限状态自动机的基本结构和模型模型并没有改变并没有改变l但使用但使用n元组表示一个状态更元组表示一个状态更为为直观和方便直观和方便。思 考：构造构造FA接收接收最后一个字符仅出现一次的语言最后一个字符仅出现一次的语言其中，其中，=a，b，c提示：需要提示：需要存储存储的信息是的信息是？