首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
admin
2015-06-03
76
问题
某一确定有限自动机(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/IP网络中,主机A和主机B通过一路由器互联,提供两主机应用层之间通信的层是(248),提供机器之间通信的层是(249),具有IP层和网络接口层的设备是(250);在A与路由器和路由器与B使用不同物理网络的情况下,主机A和路由器之间传送的数据帧与路
用于所有网络设备的完整网络管理协议族是(1),它的整体结构建立在(2)参考模型的基础上。网络管理应用进程使用该参考模型中的(3)。在该层上,公共管理信息服务单元(CMISE)提供了应用程序使用(4)协议的接口。SNMP是应用最广泛的网络管理协议,其最新版本
如图2.1所示,有四台Linux主机进行互联,则实现PC1与PC4之间互访的步骤应该是:1.首先运行(29)命令关闭计算机,在PC2与PC3上添加第二块网卡(ethl)后重新启动;2.在PC2与PC3上为第二块网卡分配IP地址,并激
ATM的155Mb/s接口中,UNI使用(41)。ATM交换机是一个多端口设备,但不可以充当(42)。SMDS是基于IEEE(43)的规范,SMDS数据分组的格式包括(44)。SMDS的说法中,(45)是不妥的。
可使网络服务器中充斥着大量要求回复的信息,消耗带宽,导致网络或系统停止正常服务,这属于(1)攻击类型。典型的针对系统漏洞的DoS攻击方式是(2)。向有限的空间输入超长的字符串是(3)攻击手段?用户收到了一封可疑的电子邮件,要求用户提供银行帐户及密码,这是属
可使网络服务器中充斥着大量要求回复的信息,消耗带宽,导致网络或系统停止正常服务,这属于(1)攻击类型。典型的针对系统漏洞的DoS攻击方式是(2)。向有限的空间输入超长的字符串是(3)攻击手段?用户收到了一封可疑的电子邮件,要求用户提供银行帐户及密码,这是属
下面关于二级目录的叙述中,错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题,通常在文件系统中采用(5)。
阅读下列说明和c++代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲实现一个图像浏览系统,要求该系统能够显示BMP、JPEG和GIF三种格式的文件,并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG
阅读下列说明和Java代码,将应填入上一处的字句写在答题纸的对应栏内。【说明】某图像预览程序要求能够查看BMP、JPEG和GIF三种格式的文件,且能够在Windows和Linux两种操作系统上运行。程序需具有较好的扩展性以支持新的文件格式和操作系统。为
两个以上的专利申请人分别就同样的发明创造在中国申请专利的,专利权授予______。
随机试题
1型糖尿病人牙周袋内龈下菌斑中主要微生物是
理财经理为客户做预算控制时,下列属于短期可控预算的是()。
某制药厂为增值税一般纳税人,2007年1—3月份发生如下经济业务:(1)1月5日销售药品价款为10万元(不含税),货款及税款已收到。(2)1月7日凭税务机关开具的收购凭证从红卫农场购进玉米100吨,每吨单价1000元,玉米当月运回企业并验收入库。(3
下列对公务员的处分的说法中,不准确的一项是()。
分数中最大的一个是()。
禀赋是指人的体魄、智力等方面的素质。下面不属于“禀赋”的是()。
有如下程序段:#includeusingnamespacestd;classA{public:intdata;staticintdata2;voidshow()
A.increasedB.releasedC.modifiedD.distributedE.browsedF.personalizedTheiPadwillonlyrunprogramsapprovedbyAppl
SpaceTourismSpaceTourismisthetermthat’scometobeusedtomeanordinarymembersofthepublicbuyingticketstotrave
Trillionsofincrediblytinydiamonds,possiblyformedbyadyingstarbeforethesolarsystemwasborn4.5billionyearsago,h
最新回复
(
0
)