首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
admin
2015-06-03
35
问题
某一确定有限自动机(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://jikaoti.com/ti/IGf7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
用于所有网络设备的完整网络管理协议族是(1),它的整体结构建立在(2)参考模型的基础上。网络管理应用进程使用该参考模型中的(3)。在该层上,公共管理信息服务单元(CMISE)提供了应用程序使用(4)协议的接口。SNMP是应用最广泛的网络管理协议,其最新版本
可以推断,该网络使用的路由算法最可能是(336)。节点A根据当前的路由信息计算出的到节点D的路由可能为(337)。将路由信息发送到其它节点所采用的基本算法是(338)。为避免路由信息被重复发送,需要给路由信息包编号。设想每秒钟传送一次路由信息,为确保路由信
当系统间需要高质量的大量数据传输时,常采用的交换方式为(1)。在屯路交换网中,利用电路交换连接起来的两个设备在发送和接收时采用(2);在分组交换网中,信息在从源节点发送到目的节点的过程中,中间节点要对分组(3)。分组交换过程中,在数据传送以前,源站和目的站
为了进行差错控制,在局域网中对数据帧广泛使用的校验方法是(178)校验。CRC-16规定的生成多项式为G(x)=X16+X15+X2+1,它产生(179)位的校验码,当接收端发现错误后会(180)。如果CRC的生成多项式为G(X)=X4+X+1,码字为10
TCP是一个面向连接的协议,它提供连接的功能是(51)的,采用(52)技术来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(53)分组,这种分组的数量最多可为(54),TCP协议采用滑动窗口协议解决了(55)。
下面关于二级目录的叙述中,错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题,通常在文件系统中采用(5)。
某CPU的主振频率为100 MHz,平均每个机器周期包含4个主振周期。各类指令的平均机器周期数和使用频度如表2.9所示,则该计算机系统的速度为平均约(5)兆指令/秒。若某项事务处理工作所要执行的机器指令数是控制程序(以访内、比较与转移等其他指令为主)220
以下关于钓鱼网站的说法中,错误的是()。
UP(UnifiedProcess)每个阶段结束时都会产生一些主要的工作成果。在初启阶段最重要的工作成果是(37)。
李富是某公司的产品设计部的设计师,他经过努力工作,研究出了一种新的产品外形,该公司利用这一设计制造出新的产品后,致使销量大增。同时,对该设计申请了专利保护,那么其专利权应该归()所有。
随机试题
Whatisyourfavoritecolor?Doyoulikeyellow,orange,red?【T1】Ifyoudo,youmustbeanoptimist,aleader,anactiveperson
当超声波从一个介质传播到另一个弹性、密度都不同于前者的介质时,声束方向将发生变化,该变化称为
由支原体引起的疾病是()。
2000年6月,最高法院决定定期向社会公布部分裁判文书,在汇编前言中指出:“最高人民法院的裁判文书,由于具有最高的司法效力,因而对各级人民法院的审判工作具有重要的指导作用,同时还可以为法律、法规的制定和修改提供参考,也是法律专家和学者开展法律教学和研究的宝
连锁经营最基本、最明显、最本质的特征()。
信用社办理支付结算,因工作差错发生延误,影响客户和他行资金使用的按中国人民银行规定的同档次()。
从业者步入职业殿堂的“通行证”,体现着从业者的道德操守和人格力量,并且还是具体行业立足的基础的是()
(00年)假设某企业在两个相互分割的市场上出售同一种产品,两个市场的需求函数分别为p1=18-2Q1,p2=12-Q2其中P1和P2分别表示该产品在两个市场的价格(单位:万元/吨),Q1和Q2分别表示该产品在两个市场的销售量(即需求量,
Writeanessayof160~200wordsbasedonthefollowingdrawing.Inyouressayyoushould:1)describethedrawingbriefly,
Afterthebirthofmysecondchild,Igotajobatarestaurant.Havingworkedwithanexperienced【C1】______forafewdays,Iw
最新回复
(
0
)