首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
admin
2009-02-15
60
问题
已知一个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)。更新路由表的
若卫星信道的数据传输率为1Mb/s,帧长为1000bit,利用卫星信道的两个站点从一方到另一方的传播时延为250ms。忽略确认帧长和处理时间,则:若帧的出错概率为0.1,而假设应答帧不出现错误,当采用停等协议时,其协议效率是(1)。若采用连续 ARQ协议,
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
某计算机系统中,16位浮点数的表示格式如图6-1所示。其中阶码4位(含1位符号)为定点整数,尾数12位(含1位符号)为定点小数,设一个数机器码为1110001010000000。若阶码为移码且尾数为原码,则其十进制数真值为(2);若阶码为补码且尾数为补
适合使用原型法开发方法的情况是(9)。
Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can
在Windows2000操作系统中,配置IP地址的命令是(53)。若用ping命令来测试本机是否安装了TCP/IP协议,则正确的命令是(54)。如果要列出本机当前建立的连接,可以使用的命令是(55)。
知识产权分为工业产权和(54),由于智力成果具有可以同时被多个主体所使用的特点,因此法律授予知识产权这种专有权具有(55),知识产权具有法定的保护期限,而商业秘密受法律保护的期限为(56),甲A未经乙B的同意擅自发表B的软件产品,甲A这种行为构成(57),
MultipurposeInternetMailExtension(MIME)isa(71)documentmessagingstandardintheInternetenviroment,withMIME,userscans
MultipurposeInternetMailExtension(MIME)is a(46)document messaging standard in the Internet enviroment, with MIME, users can
随机试题
患者男性,62岁,阵发性胸闷、气短1个月。常规心电图示窦性心动过缓。动态心电图发现夜间有显著的窦性心动过缓伴交界性逸搏心律。房室交界区的功能有
患者,女性,58岁。主因外阴部皮疹伴剧烈瘙痒4年余,加重1个月就诊。查体:心肺腹未见异常。双侧小阴唇部浸润肥厚、皲裂,呈白色,以右侧小阴唇较明显。本病诊断较有意义的检查是
一哺乳妇女,产后半年未来月经,妇查宫颈外口松,位于阴道口以上2cm,子宫稍小,双附件(-)。较好的避孕方法是( )
关于证人与鉴定人的共同特征,下列哪些选项是正确的?()
矿山企业必须从矿产品销售额中按照国家规定提取安全技术措施()。安全技术措施专项费用必须全部用于改善矿山安全技术条件,不得挪作他用。
中国证监会及其派出监管机构依法对证券公司的经纪业务进行监管,主要监管措施包括()。Ⅰ.证券公司向监管机构的报告制度Ⅱ.定期巡视Ⅲ.信息披露Ⅳ.检查制度
《中华人民共和国文物保护法》规定,具有科学价值的______化石和______化石同文物一样受国家保护。
简述拉丁方设计的特点。
TheParliamentofCanadaiscomposedof______and______.
FollowingthewarmreceptionoftheEnglishversionofPeople’sLiterature,alandmarkmagazine【C1】______(record)contemporaryC
最新回复
(
0
)