首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
admin
2009-02-15
33
问题
已知一个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)。更新路由表的
某计算机系统中,16位浮点数的表示格式如图6-1所示。其中阶码4位(含1位符号)为定点整数,尾数12位(含1位符号)为定点小数,设一个数机器码为1110001010000000。若阶码为移码且尾数为原码,则其十进制数真值为(2);若阶码为补码且尾数为补
Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can
Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can
在某路由器上已经配置了一个访问控制列表1,并且使用了防火墙功能。现在需要对所有通过Serial0接口进入的数据包使用规则1进行过滤。如下可以达到要求的是(53)。
Linux在安装了Web服务器后;当在inted下启动时,在系统文件etc/services中要添加(30),在单独运行时,命令是(31)。Web系统的系统配置文件(32)定义了服务器在DNS数据库中注册的主机名,这是通过(33)命令定义的。测试WWW服务
光缆布线系统的测试是工程验收的必要步骤。以下不是对光缆进行测试的工作内容的是(57)。
知识产权分为工业产权和(54),由于智力成果具有可以同时被多个主体所使用的特点,因此法律授予知识产权这种专有权具有(55),知识产权具有法定的保护期限,而商业秘密受法律保护的期限为(56),甲A未经乙B的同意擅自发表B的软件产品,甲A这种行为构成(57),
MultipurposeInternetMailExtension(MIME)isa(71)documentmessagingstandardintheInternetenviroment,withMIME,userscans
PriortotheavailabilityofenterpriseEDM,locatingadocumentoveraLANcouldbedifficult,andoveraWAN(66)nearlyimpossi
随机试题
关于市政消火栓布置的说法,正确的是()。
物资库房保管的基本要求有哪些?
患者,女,48岁。月经先后无定期,量或多或少,烘热汗出,五心烦热,心悸怔忡,失眠多梦,健忘,时或情志失常,舌红少苔,脉细数。方选
中国执业药师职业道德准则包括
依据行使行政立法权的主体不同,行政立法可以分为()。
A公司向B公司签发一张出票日期为10月20日、金额为100万元、出票后1个月付款的银行承兑汇票,甲银行为承兑人。11月1日,B公司将该汇票背书转让给C公司。11月5日,C公司在汇票的背面记载“不得转让”字样后,将该汇票背书转让给D公司。11月10日。D公司
一般来说,中央银行在证券市场上买卖有价证券属于()业务。
当国际收支的收入大于支出时,差额列入哪一项可以使国际收支人为地达到平衡()。(中山大学2013真题)
在考生文件夹中,对“商品销售”数据库完成如下综合应用:(1)编写名为better的命令程序并执行,该程序实现如下功能:将“商品表”进行备份,备份名称为“商品表备份.dbf”。将“商品表”中的“商品号”前两位编号为“10”的商品的单价
【S1】【S4】
最新回复
(
0
)