首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
admin
2009-02-15
43
问题
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。
表中的状态集合T是(27)。
选项
A、{1,2}
B、{3,4,5}
C、{4,5}
D、{6}
答案
B
解析
对于每个NFA M都存在一个DFA M’,使得L(M’)=L(M)
有一个方法称为子集构造法,能将一个非确定的有限自动机转换成一个等价的确定的有限自动机。
具体说来,对于给定的一个NFA M,设想有一个DFA M’,它的初态是NFA M的初态q0以及从q0出发沿空弧所能到达的那些状态,表示成I=ε_closure(q0)在M中一个状态和一个输入符号可能转换到多个状态,若在NFA M中有I×a∈∑→J
Q(表示成J=move(I,a),J是NFA M中所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体),那么,在DFA M’中设状态Ia=ε_closure(J),ε_closure(J)称为ε_闭包,其计算方法下面予以介绍。这实际上是用DFA M’模拟NFA M的动作,重复这个模拟过程,直到M’中不再增加新的状态。这个过程将逐步构造出DFA M’的状态转移矩阵表,图中NFA M的DFA M’的状态转移矩阵如表所示。
ε_closure(T)称为子集T的ε_闭包,计算方法如下:
(1)ε_closure(T)=T;
(2)
q∈ε_closure(T),若δ(q, ε)=q’,则把q’加到ε_closure(T)中,直到ε_closure(T)不再增大为止。也就是说,ε_closure(T)不仅含有T,而且含有从T出发沿空弧所能到达的所有状态,直观理解是去掉NFA M的空弧。
表中I是M状态集的一个子集,首先求DFA M’的初态,表[0,0]=ε_closure(0)={0,1,2},然后求I0和I1。表[0,1]=ε_closurre(move({0,1,2},0))=ε_closure({1})={1,2}表[0,2]=ε-closure(move({0,1,2},1))=ε_closure({3})={3,4,5}
如果I0和I1不出现在表的第1列I中,则把它们填入第1列I下面的空行位置上。之后,对I的新行上的子集重复求I0和I1,直至所有第2列和第3列的子集全都在第1列中出现为止。这个过程必定在有限步内终止,因为M的状态子集的个数是有限的。
T=ε_closure(move({1,2},1))=ε_closure(move({3})={3,4,5}。
转载请注明原文地址:https://kaotiyun.com/show/DJxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
安全的威胁可分为两大类,即主动攻击和被动攻击。通过截取以前的合法记录稍后重新加入一个连接,叫做重放攻击。为防止这种情况,可以采用的办法是(6)。一个计算机系统被认为是可信任的,主要从其受保护的程度而盲的,Windows NT 4.0以上版本目前具有的安全等
若卫星信道的数据传输率为1Mb/s,帧长为1000bit,利用卫星信道的两个站点从一方到另一方的传播时延为250ms。忽略确认帧长和处理时间,则:若帧的出错概率为0.1,而假设应答帧不出现错误,当采用停等协议时,其协议效率是(1)。若采用连续 ARQ协议,
网桥是用来连接同介质局域网的关键网络设备,无需用户设置的网桥称为“透明网桥”。当网桥从某个端口收到正确的数据帧之后,将在其地址表中查找该帧要到达的目地站的MAC地址,若找不到,则(66),若发现其也在该端口的转发表中,则(67)。当网络中的网桥形成环路时,
网桥是用来连接同介质局域网的关键网络设备,无需用户设置的网桥称为“透明网桥”。当网桥从某个端口收到正确的数据帧之后,将在其地址表中查找该帧要到达的目地站的MAC地址,若找不到,则(66),若发现其也在该端口的转发表中,则(67)。当网络中的网桥形成环路时,
Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can
一个带宽为3kHz、没有噪声的信道传输二进制信号时能够达到的极限数据数率为(14)。一个带宽为3kHz、信噪比为30dB的信道能够达到的极限数据传输率为(15)。上述结果表明,(16)。根据奈奎斯特第一定理可知,为了保证传输质量,达到3kb/s的数据传
用原型法开发一个管理信息系统,评价原型阶段的主要任务是(7)。
在软件的生命周期中,下列说法错误的是(37)。
MultipurposeInternetMailExtension(MIME)isa(71)documentmessagingstandardintheInternetenviroment,withMIME,userscans
MultipurposeInternetMailExtension(MIME)isa(71)documentmessagingstandardintheInternetenviroment,withMIME,userscans
随机试题
全脂奶粉加开水冲调,使其成分与鲜牛奶相似,其容积比应是
生物碱在植物体内的存在形式有
属于传统医学典籍的有()。
装运经国家批准进口的废物原料的集装箱,应当由( )实施检验检疫。
甲公司2017年5月25日向乙公司购买了一处位于郊区的厂房,随后出租给丙公司。甲公司以自有资金向乙公司支付总价款的30%,同时甲公司以该厂房作为抵押向丁银行借入余下的70%价款。这种租赁方式是()。
假如你是一位乡镇党委秘书,让你组织一次会议。你如何进行?
下列各句中,加点的成语使用恰当的一句是:
多元系统理论的来源不包括()。
冯.诺伊曼(VonNeumann)在总结ENIAC的研制过程和制定EDVAC计算机方案时,提出两点改进意见,它们是______。
A、 B、 C、 C本题的关键词是goinside,failed。
最新回复
(
0
)