首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
已知一个NFA M图如下所示,采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T
admin
2009-02-15
31
问题
已知一个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
软件设计师上午基础知识考试
软考中级
相关试题推荐
网桥是用来连接同介质局域网的关键网络设备,无需用户设置的网桥称为“透明网桥”。当网桥从某个端口收到正确的数据帧之后,将在其地址表中查找该帧要到达的目地站的MAC地址,若找不到,则(66),若发现其也在该端口的转发表中,则(67)。当网络中的网桥形成环路时,
在计算机指令系统中,通常采用多种确定操作数的方式。当操作数直接给出时,这种寻址方式叫做(2);当操作数的地址由某个指定的变址寄存器的内容与位移量相加得到时,叫做(3);如果操作数的地址是主存中与该指令地址无关的存储单元的内容,则叫做(4)。
在MIB-2功能组的接口组中,表征某个交换机端口的状态为故障时,对象(42)。
Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can
ISO9000资质认证过程中要对企业的各方面进行严格审查,还要每年进行自检和外检。ISO9000质量管理体系认证证书的有效期为(6)。
光缆布线系统的测试是工程验收的必要步骤。以下不是对光缆进行测试的工作内容的是(57)。
利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。以下是某台交换机(Switch)的部分配置过程,其中空缺处的命令/参数可能是(48)。Switch#vlandatabaseSwi
在安装ApacheWeb安全服务器软件包时,想通过安全套接字层(SSL)和传输层安全(TLS)协议为ApacheWeb服务器提供强大的加密能力,则需要启动(30)软件包。
MultipurposeInternetMailExtension(MIME)isa(71)documentmessagingstandardintheInternetenviroment,withMIME,userscans
PriortotheavailabilityofenterpriseEDM,locatingadocumentoveraLANcouldbedifficult,andoveraWAN(66)nearlyimpossi
随机试题
下列对看守内阁的描述中,不正确的是()
StomachUlcerStomachulcers(溃疡)arethecauseofseverepainformanypeople.Doctorshavebeenabletohelplessenthepai
在离子通道介导的跨膜信号转导系统中,错误的是
建立项目法人责任制的目的有()。
隧道的施工方法是隧道主要分类依据之一,其可分为()等。
汉译英:“动植物检疫;宰前兽医检验”,正确的翻译为:( )
某增值税一般纳税企业自建一幢仓库,购入工程物资100万元,增值税额为17万元,已全部用于建造仓库;耗用库存材料50万元,应负担的增值税额为8.5万元,支付建筑工人工资28万元。该仓库建造完成并达到预定可使用状态,其入账价值为()万元。
根据反垄断法律制度的规定,下列关于市场支配地位推定的表述中,不正确的是()。
有以下程序#include#includeintfun(intn){int*p;p=(int*)malloc(sizeof(int));*p=n;return*p;}mai
DemonstratorsrallyatLosAngelesCityHallduringthefirstWomen’sMarch,heldonJan.21,2017,onedayafterPresidentTrum
最新回复
(
0
)