首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
admin
2015-06-03
54
问题
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
选项
A、10*(0|1)*
B、((0*0)*1*)*
C、1*((0|1)00)*
D、(1*(01*0)*)*
答案
D
解析
本题主要考察有限自动机和正规式,这个知识点也是考试中的重点和难点。
对于判断一个有限自动机与那个正规式等价,常见的方法是分析有限自动机,清楚有限自动机所表示的含义和特性,然后用排除法找到与该有限自动机等价的正规式。
对于本题,首先分析题目中给出的状态转换图,由图可知,状态q0为唯一的终态,也是初态,那么从初态到终态可以不输入然后字符,因此该有限自动机可识别空串。
另外,仔细分析有限自动机,不难发现,以一个0离开状态q0然后再以一个0返回状态q0。那么从初态到终态输入0的个数必须是偶数,而该有限自动机只能识别0和1两种字符。因此该自动机识别的串是包含偶数0的二进制代码串。
清楚了该有限自动机的特性和含义后,我们再逐个分析四个正规式。
在正规式1*0(0|1)木中,不能确保O的个数是偶数,而不能表示空串(因为所有闭包取空,结果仍然有一个1),因此这个正规式肯定不与有限自动机等价。
在正规式((0*0)*1*)*中,可以表示空串,但不能确保O的个数是偶数,因此也不等价于题目给出的有限自动机。
同样的道理,可知正规式1*((0|1)00)*也不与题目给出的有限自动机等价。
而在正规式(1*(01*0)*)*中,即可以表示空串,也由于(01*0)这部分不管重复多少次,都能确保0的个数是偶数,因此等价。
转载请注明原文地址:https://kaotiyun.com/show/WCRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
TCP是一个面向连接的协议,它提供连接的功能是(51)的,采用(52)技术来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(53)分组,这种分组的数量最多可为(54),TCP协议采用滑动窗口协议解决了(55)。
在TCP/IP的网路体系结构中,各个层次提供不同可靠性的网络服务,其中,IP协议提供主机之间的(312)分组传输服务。TCP协议提供端口之间的(313)报文传输服务;为了实现可靠的服务,采用超时重传、确认捎带技术。传输中的协议规定,在确认信息中捎带(314
在TCP/IP的网路体系结构中,各个层次提供不同可靠性的网络服务,其中,IP协议提供主机之间的(312)分组传输服务。TCP协议提供端口之间的(313)报文传输服务;为了实现可靠的服务,采用超时重传、确认捎带技术。传输中的协议规定,在确认信息中捎带(314
如图3.1所示,如果为曼彻斯特编码,则表示的数据可能为(283),下面的各种网络中,适用这种编码的是(284)。为了在广域网上高速传输数字信号,可用(285)的编码方式,其编码效率为(286)。设某编码体制的编码方法为:输入数据(m=1,2,…),发送时,
码字之间的海明距离是指(148),一个码(码是一些码字组成的集合)的海明距离是所有不同码字的海明距离的(149)。如果要检查出d位错,那么码的海明距离是(150)。如果信息长度为6位,要求纠正1位错,按照海明编码;需要增加的校验位是(151)。以太网中使用
依据《计算机软件保护条例》,对软件的保护包括()。
编译和解释是实现高级程序设计语言的两种基本方式,()是这两种方式的主要区别。
知识产权一般都具有法定的保护期限,一旦保护期限届满,权利将自行终止,成为社会公众可以自由使用的知识。(20)权受法律保护的期限是不确定的,一旦为公众所知悉,即成为公众可以自由使用的知识。
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句填写完整。[说明](1)对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,可构造如
类比二分搜索算法,设计k分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,……,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得到
随机试题
壁细胞分泌的物质有
A.累及部位多,症状出现的频繁,对患儿情绪、心理影响较大B.症状持续时间较长,但对患者社会功能影响相对较小C.预后良好,大多数患儿症状自行好转D.大多数患者症状持续终生E.病情严重,部分患儿会过早夭折慢性运动或发声抽动障碍
下列哪项不应作会阴切开
对历史文化保护区内重点保护地段的建设控制指标和规定,是城市()内容。
根据《建设工程工程量清单计价规范》,一般情况下,编制招标控制价采用的材料优先选用()。
税收能否转嫁及转嫁的程度,受()等因素的影响与制约。
某地大雪,一小区水管、电线被冻坏,居民到居委会闹事,你是居委会负责人。你怎么办?
将200块糖分给甲、乙、丙三人,甲的糖比乙的2倍还要多,乙的糖比丙的3倍还要多,甲至少有多少块糖?
根据我国现行宪法和法律,以下可以具有中国国籍的是()。
有些外科手术需要一种特殊类型的线带,使外科伤口缝合达到10天,这是外科伤口需要线带的最长时间。D型带是这种线带的一个新品种。D型带的销售人员声称D型带将会提高治疗功效,因为D型带的黏附时间是目前使用的线带的两倍长。以下哪项如果成立,最能说明D型带销售
最新回复
(
0
)