首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
有限自动机(FA)可用于识别高级语言源程序中的记号(单词),FA可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D与某NFA M等价,则(48)。
有限自动机(FA)可用于识别高级语言源程序中的记号(单词),FA可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D与某NFA M等价,则(48)。
admin
2021-01-13
31
问题
有限自动机(FA)可用于识别高级语言源程序中的记号(单词),FA可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D与某NFA M等价,则(48)。
选项
A、DFA D与NFA M的状态数一定相等
B、DFA D与NFA M可识别的记号相同
C、NFA M能识别的正规集是DFA D所识别正规集的真子集
D、DFA D能识别的正规集是NFA M所识别正规集的真子集
答案
B
解析
本题考查程序语言翻译基础知识。非确定有限自动机NFA是一个五元组(5-tuple):M=(S,∑,move,s0,F)其中,①S是有限个状态(state)的集合;②∑是有限个输入字符(包括ε)的集合:③move是一个状态转移函数,move(si,ch)=sj表示,当前状态si下若遇到输入字符ch,则转移到状态即④sj;④s0是唯一的初态(也称开始状态);⑤F是终态集(也称接受状态集),它是S的子集,包含了所有的终态。确定的有限自动机DFA是WA的特例:①DFA没有状态具有ε状态转移(ε-transition),即状态转换图中没有标记ε的边;②对每一个状态s和每一个字符a,最多有一个下一状态。若两个FA识别同一个正规集,则这两个FA等价。对于每个NFA,都存在与之等价的DFA。
转载请注明原文地址:https://kaotiyun.com/show/XkCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某公司拟开发一套小区物业收费管理系统。初步的需求分析结果如下:(1)业主信息主要包括:业主编号,姓名,房号,房屋面积,工作单位,联系电话等。房号可唯一标识一条业主信息,且一个房号仅
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某物流公司为了整合上游供应商与下游客户,缩短物流过程,降低产品库存,需要构建一个信息系统以方便管理其业务运作活动。【需求分析结果】(1)物流公司包含若干部门,部门信息包括部门号、
阅读下列说明和图,回答问题1至问题3。【说明】某会议策划公司为了方便客户,便于开展和管理各项业务活动,需要构建一个基于网络的会议预定系统。【需求分析】(1)会议策划公司设有受理部、策划部和其他部门。部门信息包括部门号
阅读下列说明和图,回答问题1~问题3,将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSeg
阅读下列说明和C代码,回答问题。【说明】n一皇后问题是在n行n列的棋盘上放置n个皇后,使得皇后彼此之间不受攻击,其规则是任意两个皇后不在同一行、同一列和相同的对角线上。拟采用以下思路解决n.皇后问题:第i个皇后放在第i行。从第一个皇后
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某物流公司为了整合上游供应商与下游客户,缩短物流过程,降低产品库存,需要构建一个信息系统以方便管理其业务运作活动。【需求分析结果】(1)物流公司包含若干部门,部门信息包括部门号、
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下。对于n个元素的关键字序列{a1,a2……,an},当且仅当满足下列关系时称其为堆:在一个堆中,若堆项元素为最大元素,
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。【说明】假币问题:有n枚硬币,其中有一枚是假币,已知假币的重量较轻。现只有一个天平,要求用尽量少的比较次数找出这枚假币。【分析问题】将n枚硬币分成相等的两部分:(1)当n为偶数时,将
某一非确定性有限自动机(NFA)的状态转换图如下图所示,与该NFA等价的正规式是(28),与该NFA等价的DFA是(29)。
随机试题
Itisnaturalforyoungpeopletobecriticaloftheirparentsattimesandtoblamethemformostofthemisunderstandingsbetw
虚证晕厥的配穴为
A.变质性炎B.卡他性炎C.假膜性炎D.肉芽肿性炎E.化脓性炎伤寒
下列行为中,依法构成强奸罪的有:
建筑装饰装修工程施工()不经穿管直接埋设电线。
以下各项不属于素质测评中对员工进行分类的标准的是()。
求I=,其中∑为上半球z=的上侧,a>0为常数.
Forachild,happinesshasamagicalquality.Iremembermakinghide-outsinnewlycuthay,playingcopsandrobbersinthewood
以下构成Python循环结构的方法中,正确的是()。
Itisn’texpectedtostartnibblingawayatcomputerdatasystemsuntilthedocksclickoverto2000,butthemillenniumbughas
最新回复
(
0
)