首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
admin
2009-02-15
47
问题
已知一个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
软件设计师上午基础知识考试
软考中级
相关试题推荐
路由信息协议RIP是内部网关协议IGP中使用得最广泛的一种基于(21)的协议,其最大优点是(22)。RIP规定数据每经过一个路由器,跳数增加1,实际使用中,一个通路上最多可包含的路由器数量是(23),更新路由表的原则是使到各目的网络的(24)。更新路由表的
安全的威胁可分为两大类,即主动攻击和被动攻击。通过截取以前的合法记录稍后重新加入一个连接,叫做重放攻击。为防止这种情况,可以采用的办法是(6)。一个计算机系统被认为是可信任的,主要从其受保护的程度而盲的,Windows NT 4.0以上版本目前具有的安全等
若卫星信道的数据传输率为1Mb/s,帧长为1000bit,利用卫星信道的两个站点从一方到另一方的传播时延为250ms。忽略确认帧长和处理时间,则:若帧的出错概率为0.1,而假设应答帧不出现错误,当采用停等协议时,其协议效率是(1)。若采用连续 ARQ协议,
若卫星信道的数据传输率为1Mb/s,帧长为1000bit,利用卫星信道的两个站点从一方到另一方的传播时延为250ms。忽略确认帧长和处理时间,则:若帧的出错概率为0.1,而假设应答帧不出现错误,当采用停等协议时,其协议效率是(1)。若采用连续 ARQ协议,
1台服务器、3台客户机和2台打印机构成了一个局域网(如图5-6所示)。在该系统中,服务器根据某台客户机的请求,将数据在一台打印机上输出。设服务器、各客户机及各打印机的可用性分别为a、b、c,则该系统的可用性为(60)。
ISO9000资质认证过程中要对企业的各方面进行严格审查,还要每年进行自检和外检。ISO9000质量管理体系认证证书的有效期为(6)。
虚拟存储管理系统的基础是程序的(23)理论,这个理论的基本含义是指程序执行时往往会不均匀地访问主存储器单元。根据这个理论,Denning提出了工作集理论。工作集是进程运行时被频繁地访问的页面集合。在进程运行时,如果它的工作集页面都在(24)内,能够使该进程
(41)是在一个公司发给另一个公司的报文上,连同报文和签名一起做一个摘要的方法。目前的产品能够做到的最高安全级别是(42)级。仔细阅读日志属于(43)的内容。在网络安全策略中,属于半主动网络安全策略的方法是(44)。在故障报告中,设备运行出现错误状态用(4
在软件的生命周期中,下列说法错误的是(37)。
MultipurposeInternetMailExtension(MIME)is a(46)document messaging standard in the Internet enviroment, with MIME, users can
随机试题
某矿区地下矿产资源极为丰富,自2008年以前即由当地居民进行小规模零星开采,2008年当地的村镇企业将全部的民采整合后挂牌成立了一家集体所有制的采矿企业甲。在成立初期采用竖井、平硐联合开拓方式,采用JKA型矿井提升机进行提升,辅以采用装载机和汽车直接进人
疲劳骨折最好发部位是
《中华人民共和国职业病防治法》开始实施的时间是
患者,女,26岁。现症见面色灰白,恍惚神昏,汗出身冷,四肢厥逆,口燥咽干,肌肤干皱,尿少或无尿。舌淡或光红无苔,脉微欲绝。查体:血压70/60mmHg,神志欠清,四肢湿冷。其治法是()
3岁男童,母亲为之穿衣牵拉右手臂后突然哭闹,不敢屈肘持物,其诊断应首先考虑
任何一项分部分项工程在施工前,工程技术人员都应根据施工组织设计的要求,编写有针对性的(),由施工员对班组工人进行交底。
FIDIC分包合同中规定,承包商就分包合同的索赔对分包商承担责任的先决条件是( )。
ABC公司对某投资项目的分析与评价资料如下:该投资项目适用的所得税税率为25%,年税后营业收入为525万元,税后付现成本为370万元,税后营业利润80万元。那么,该项目年营业现金净流量(税后)为()万元。
Inthesamewaythatachildmustbeabletomovehisarmsandlegsbeforehecanlearntowalk,thechildmustphysiologically
Whatdoesthemanwantthewomantodo?
最新回复
(
0
)