有穷状态自动机-电子科技大学

《有穷状态自动机-电子科技大学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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。这一过程记作：xqayxapyDFA的构造设M=(Q,,,q0,F)为一个FA，对qQ，能引导FA从开始状态到达q的字符串的集合为set(q)={x

2、x*,(q0,x)=q}出现语言不能接受的序列时进入陷井状态qt构造语言的DFA。3.3不确定的有穷状态自动机作为对

3、DFA的修改构造接受语言L={x

4、x{0,1}*,且x含有子串00或11}的DFASq00q1q2q30110,110“直接”的FASq00q1q2q300,10,111希望是接受语言L={x

5、x{0,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。当这个子集为空时，表示没有状态与之对应

6、；当这个子集的元素个数大于1时，表示有多个状态与之对应。当这个子集元素个数为1时，退化为DFA。从这个意义上，(q,a)仍是通常意义下的一个函数，只是其值域发生了改变。这种“FA”的特点Sq00q1q2q300,10,111具有“智能”：可根据当前从输入字符串读入的字符自动地选择进入一个正确的状态。这种“FA”的特点具有“智能”只要在FA中存在一条从开始状态出发，最终到达某一个终止状态的标记为x的路径，就认为它接受了串x，否则认为它不接受串x。从这个意义上来说，这类FA与DFA的作用是一致的(识别句子是否合法)。NFA的形式定义定义3-7不确定的有穷状态自动机(non-

7、deterministicfiniteautomaton,NFA)M是一个五元组：M=(Q,,,q0,F)其中，Q,,q0,F状态的意义同DFA(定义3-1)—状态转移函数。:Q2Q。对(q,a)Q，(q,a)={p1,p2,…,pm}表示M在状态q读入字符a，可以选择地将状态变成p1,p2,…,或者pm，并将读头向右移动一个带方格而指向输入字符串的下一个字符。扩充将扩充为：Q*2Q。对qQ，w*，a：(1)(q,)={q}(2)(q,wa)={p

8、r(q,w),st.p(r,a)}扩充的作用：(1)加入单位元素(

9、2)从概念上允许一次接收字母表的任意一个字符串，而不仅是一个字符与“兼容”的定义域Q是的定义域的Q*真子集，需要考虑在上Q，是否与有相同的函数值：(q,a)=(q,a)={p

10、r(q,),st.p(r,a)}根据(2)={p

11、r{q},st.p(r,a)}根据(1)={p

12、p(q,a)}q是r唯一可能值=(q,a)因此与“兼容”。约定：以后直接用代替。进一步扩充将进一步扩充为:2Q*2Q。对PQ，w*:(P,w)=(q,w)扩充的意义：从概念上可以处理一个状态集合对某一字符串的“反应”。如：模4余0的

13、例子中，无论是什么状态下接收了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

14、x*且(q0,x)FØ}称为由M接受(识别)的语言。练习(见习题)10.(1)构造识别语言L={x

15、x{0,1}+,且x中不含形如00的子串的NFA习题评讲10.(1)Sq0q20,100,10q1本答案错误，因为任意串均可以到达q0习题评讲(续)10.(1)正确答案与2.(3)相同，因为D

16、FA是NFA的特例(把状态q3去掉也可以)Sq01q110,1q30q2001分析NFA适于构造“包含子串…”，“以串…开始，串…结束”，“(倒数)第…个字母是…”，“满足条件…”的语言；NFA不适于构造“不包含子串…”，“不满足条件…”的语言，在这些情况下它可能退化为DFA。定理3-1NFA与DFA等价。NFA与DFA等价是指NFA和DFA能识别相同的语言类。回顾等价的概念：识别相同的语言(定义3-3)。证明思路(1)显然，DFA是NFA的特殊形式；即所有的DFA已经用NFA的形式表示；(2)需要证明对于任意给定的NFA，