首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
admin
2009-02-15
42
问题
已知一个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
软件设计师上午基础知识考试
软考中级
相关试题推荐
若卫星信道的数据传输率为1Mb/s,帧长为1000bit,利用卫星信道的两个站点从一方到另一方的传播时延为250ms。忽略确认帧长和处理时间,则:若帧的出错概率为0.1,而假设应答帧不出现错误,当采用停等协议时,其协议效率是(1)。若采用连续 ARQ协议,
网桥是用来连接同介质局域网的关键网络设备,无需用户设置的网桥称为“透明网桥”。当网桥从某个端口收到正确的数据帧之后,将在其地址表中查找该帧要到达的目地站的MAC地址,若找不到,则(66),若发现其也在该端口的转发表中,则(67)。当网络中的网桥形成环路时,
光纤通信中使用的复用方式是(20)。E1载波把32个信道按(21)方式复用在一条2.048Mb/s的高速信道上,每条话音信道的数据速率是(22)。
某计算机系统中,16位浮点数的表示格式如图6-1所示。其中阶码4位(含1位符号)为定点整数,尾数12位(含1位符号)为定点小数,设一个数机器码为1110001010000000。若阶码为移码且尾数为原码,则其十进制数真值为(2);若阶码为补码且尾数为补
设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,那么采用二级索引结构搜索文件内容时,可寻址的文件最大长度为(40)。
Internet网在通信子网内实现数据报操作方式对端系统(24)。
一个带宽为3kHz、没有噪声的信道传输二进制信号时能够达到的极限数据数率为(14)。一个带宽为3kHz、信噪比为30dB的信道能够达到的极限数据传输率为(15)。上述结果表明,(16)。根据奈奎斯特第一定理可知,为了保证传输质量,达到3kb/s的数据传
软件开发中的瀑布模型典型地刻画了软件生存周期各个阶段的划分,与其最相适应的软件开发方法是(9)。
PriortotheavailabilityofenterpriseEDM,locatingadocumentoveraLANcouldbedifficult,andoveraWAN(66)nearlyimpossi
随机试题
施工前,应按照()比例将管道内减阻涂料基料和固化剂搅拌均匀。
郁达夫所创作的散文名篇有
在X线摄影中,光电效应的优势是
按照年金的支付时间和支付金额是否确定,年金可分为()年金。
某施工单位承担了一井筒的施工项目,该工程项目施工合同价为560万元,合同工期为6个月,施工合同规定:(1)开工前业主向施工单位支付合同价20%的预付款。(2)业主自第1个月起,从施工单位的应得工程款中按10%的比例扣保留金,保留金限额暂
为隧道供电的柴油发电机房设置的储油间,应采用防火墙和能自行关闭的()防火门与发电机房和其他部位分隔开。
某铜矿开采企业为增值税一般纳税人,2019年3月生产经营情况如下:采用分期收款方式销售自采铜矿2000吨,不含增值税单价0.06万元/吨,合同约定本月收回货款的60%,其余货款下月10日收回。销售铜矿原矿加工的铜精矿50吨,取得不含税销售额180万元,该企
在中国境内居留的外国人申请延长居留期限的,应当在居留证件有效期限届满()日前向居留地县级以上地方人民政府公安机关出入境管理机构提出申请。
0.5,2,,8,()
Mikewasveryrespectfulathomeand______tohisparents.
最新回复
(
0
)