首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是( )。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是( )。
admin
2017-08-31
50
问题
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是( )。
选项
A、10*(0|1)*
B、((0.0)*1*)*
C、1*((011)00)*
D、(1*(01*0)*)*
答案
D
解析
本题主要考察有限自动机和正规式,这个知识点也是考试中的重点和难点。
对于判断一个有限自动机与那个正规式等价,常见的方法是分析有限自动机,清楚有限自动机所表示的含义和特性,然后用排除法找到与该有限自动机等价的正规式。
对于本题,首先分析题目中给出的状态转换图,由图可知,状态q0为唯一的终态,也是初态,那么从初态到终态可以不输入然后字符,因此该有限自动机可识别空串。
另外,仔细分析有限自动机,不难发现,以一个0离开状态q0然后再以一个0返回状态q0。那么从初态到终态输入0的个数必须是偶数,而该有限自动机只能识别0和1两种字符。因此该自动机识别的串是包含偶数0的二进制代码串。
清楚了该有限自动机的特性和含义后,我们再逐个分析四个正规式。
在正规式1*0(011)*中,不能确保0的个数是偶数,而不能表示空串(因为所有闭包取空,结果仍然有一个1),因此这个正规式肯定不与有限自动机等价。
在正规式((0*0)*1木)木中,可以表示空串,但不能确保0的个数是偶数,因此也不等价于题目给出的有限自动机。
同样的道理,可知正规式1*((0|1)00)*也不与题目给出的有限自动机等价。
而在正规式(1*(01*0)*)*中,即可以表示空串,也由于(01*0)这部分不管重复多少次,都能确保0的个数是偶数,因此等价。
转载请注明原文地址:https://kaotiyun.com/show/9NRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
RIP是一种基于(1)算法的路由协议,一个通路上最大跳数是(2),更新路由表的原则是到各个目标网络的(3)。(1)
I/O系统主要有(24)、(25)和(26)三种方式来与主机交换数据。其中(24)主要用软件方法来实现,CPU的效率低;(25)要有硬件和软件两部分来实现,它利用专门的电路向CPU中的控制器发出I/O服务请求,控制器则(27)转入执行相应的服务程序;(26
现采用四级流水线结构分别完成一条指令的取指、指令译码和取数、运算以及送回运算结果四个基本操作,每步操作时间依次为60ns、100ns、50ns和70ns。该流水线的操作周期应为(20)ns。若有一小段程序需要用20条基本指令完成(这些指令完全适合于在流水线
在数据的两种交换方式中,分组交换与线路交换相比,最大的优点是(238),最大的缺点是(239)。设待传送数据总长度为L位、分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个链路上的延迟时间为D秒,数据传输率为B位/秒,线路交换和
下面关于著作权的描述,不正确的是()。
数据字典是在结构化分析方法中的重要文档。数据字典的组成内容之一就是对加工的描述,常用的加工描述方法(6)。
Wi-Fi联盟制定的安全认证方案WPA(Wi-FiProtectedAccess)是__________标准的子集。(2011年上半年试题)
在异步通信中,每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位,每秒钟传送100个字符,采用DPSK调制,则码元速率为(1),有效数据速率为(2)。(1)
若计算机存储数据采用的是双符号位(00表示正号、11表示负号),两个符号相同的数相加时,如果运算结果的两个符号位经(3)运算得1,则可断定这两个数相加的结果产生了溢出。
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得
随机试题
患者,女,28岁,孕30周。近1周四肢水肿,肤色咣白,皮薄光亮,纳差便溏,神疲乏力,舌质淡胖,边有齿痕,苔薄白,脉缓滑无力,测血压145/90mmHg,尿蛋白(+),诊断为轻度妊高征,治疗最佳选方为
根据合同通用条款规定的文件解释优先顺序,下列文件中具有最优先解释权的是()。
[1998年第004题]影响空间组合的外因很多,下列哪一条不属于此一范畴?
下列关于投资型保险产品的说法,错误的是()。
鱼的脂肪含有大量的________,可以将动脉粥样硬化斑点上的________移走,从而起到预防心血管疾病的作用。
筒述柏拉图《理想国》中的教育观。
依据载人登月的三个可能时间表,我国载人登月最早可能在2020年实现。
试证方程2x一x2=1有且仅有三个实根.
Passwordsareapainintheass.They’reeithereasyto【C1】______orhardtoremember,andwhenbreaches(破坏)【C2】______youhave
A、20dollars.B、100dollars.C、1,982dollars.D、60,000dollars.D
最新回复
(
0
)