《第03章有穷状态自动机电子科技大学.ppt》由会员分享，可在线阅读，更多相关《第03章有穷状态自动机电子科技大学.ppt（34页珍藏版）》请在三一办公上搜索。
1、即时描述,设M=(Q,q0,F)为一个FA，x,y*，(q0,x)=q，xqy称为M的一个即时描述。它表示xy是M 正在处理的一个字符串，x引导M从q0启动并到达状态q，当前正指向y的首字符。如果xqay是M的一个即时描述，且(q,a)=p，则经过字符a的处理后，即时描述变为xapy。这一过程记作：xqay xapy,DFA的构造,设M=(Q,q0,F)为一个FA，对q Q，能引导FA从开始状态到达q的字符串的集合为set(q)=x|x*,(q0,x)=q出现语言不能接受的序列时进入陷井状态qt构造语言的DFA。,3.3 不确定的有穷状态自动机,作为对DFA的修改,构造接受语言L=x|x0,1
2、*,且 x含有子串00或11的DFA,“直接”的FA,希望是接受语言L=x|x0,1*,且 x含有子串00或11的FA,与DFA的区别,并不是对于所有的(q,a)Q，(q,a)都有一个状态与之对应(相当于f(x)对某些x没有函数值)；并不是对于所有的(q,a)Q，(q,a)都只对应一个状态(相当于f(x)对某些x有多个函数值)。,理解这种“FA”,(q,a)对应的是状态的一个子集，即x 2Q。当这个子集为空时，表示没有状态与之对应；当这个子集的元素个数大于1时，表示有多个状态与之对应。当这个子集元素个数为1时，退化为DFA。从这个意义上，(q,a)仍是通常意义下的一个函数，只是其值域发生了改变
3、。,这种“FA”的特点,具有“智能”：可根据当前从输入字符串读入的字符自动地选择进入一个正确的状态。,这种“FA”的特点,具有“智能”只要在FA中存在一条从开始状态出发，最终到达某一个终止状态的标记为x的路径，就认为它接受了串x，否则认为它不接受串x。从这个意义上来说，这类FA与DFA的作用是一致的(识别句子是否合法)。,NFA的形式定义,定义3-7 不确定的有穷状态自动机(non-deterministic finite automaton,NFA)M是一个五元组：M=(Q,q0,F)其中，Q,q0,F 状态的意义同DFA(定义3-1)状态转移函数。:Q 2Q。对(q,a)Q，(q,a)=p
4、1,p2,pm 表示M在状态q读入字符a，可以选择地将状态变成p1,p2,或者pm，并将读头向右移动一个带方格而指向输入字符串的下一个字符。,扩充,将扩充为：Q*2Q。对q Q，w*，a：(1)(q,)=q(2)(q,wa)=p|r(q,w),st.p(r,a)扩充的作用：(1)加入单位元素(2)从概念上允许一次接收字母表的任意一个字符串，而不仅是一个字符,与“兼容”,的定义域Q 是 的定义域的Q*真子集，需要考虑在上Q，是否与有相同的函数值：(q,a)=(q,a)=p|r(q,),st.p(r,a)根据(2)=p|r q,st.p(r,a)根据(1)=p|p(q,a)q是r唯一可能值=(q,
5、a)因此 与“兼容”。约定：以后直接用代替。,进一步扩充,将进一步扩充为:2Q*2Q。对P Q，w*:(P,w)=(q,w)扩充的意义：从概念上可以处理一个状态集合对某一字符串的“反应”。如：模4余0的例子中，无论是什么状态下接收了00，都会转到q0。更深的意义可借助定理3-1的证明及例3-7体会。,定义3-8,设M=(Q,q0,F)为一个NFA。对于x*：如果(q0,x)F，则称x 被M所接受；如果(q0,x)F=，则称M不接受x。L(M)=x|x*且(q0,x)F 称为由M接受(识别)的语言。,练习(见习题),10.(1)构造识别语言L=x|x0,1+,且 x中不含形如00的子串的NFA,
6、习题评讲,10.(1),本答案错误，因为任意串均可以到达q0,习题评讲(续),10.(1)正确答案与2.(3)相同，因为DFA是NFA的特例(把状态q3去掉也可以),分析,NFA适于构造“包含子串”，“以串开始，串结束”，“(倒数)第个字母是”，“满足条件”的语言；NFA不适于构造“不包含子串”，“不满足条件”的语言，在这些情况下它可能退化为DFA。,定理3-1,NFA与DFA等价。NFA与DFA等价是指NFA和DFA能识别相同的语言类。回顾等价的概念：识别相同的语言(定义3-3)。,证明思路,(1)显然，DFA是NFA的特殊形式；即所有的DFA已经用NFA的形式表示；(2)需要证明对于任意给
7、定的NFA，存在与之等价的DFA。根据NFA构造DFA，将状态集合从Q变换到2Q，这样DFA中的任意一个状态实际上是NFA中某些状态的组合(这里避免使用术语“集合”)。使用归纳法证明DFA与NFA的状态转移存在一一对应关系。证明由DFA和NFA能识别相同的语言。L(M1)=L(M2),例3-7,求与下图所示NFA等价的DFA。,例3-7(续),从q0开始可以到达的状态为可达状态,对于DFA来说，只有可达状态才有用。分析：DFA的一个状态对应NFA的一个状态集合，因此，需要24=16个状态。下表列出其状态转移。,例3-7(续),例3-7(续),例3-7(续),获得的DFA。,S,q0,0,q0,
8、q1,0,0,1,1,q0,q2,1,0,q0,q1,q3,0,1,q0,q2,q3,1,例3-7(续),简化后的DFA。,例3-7(续),减少工作量的方法只列出可达状态的转移，即填表时不需要填完填表时可用0,1代替q0,q1 总是不可达的，可将该状态对应的转移去掉说明这种记法主要是为了保持上下文一致，实际上它与q0,q1应有所区别。,练习(见习题),11.(1)(去掉输入字母2)要求：画出NFA状态转移图；构造DFA，获取其转移函数；画出状态转移图；化简DFA。,NFA的状态转移函数如下，构造与之等价的DFA,习题评讲(续),NFA,习题评讲,习题评讲(续),习题评讲(续),DFA,S,q0,0,q0,q1,0,1,1,q0,q2,1,0,q0,q1,q3,0,q0,q1,q2,q3,0,1,1,q0,q2,q3,0,1,习题评讲(续),化简后的DFA,作业(见习题),10.(2)(5),
