首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
某一确定有限自动机(DFA)的状态转换图如图2-2所示,与该DFA等价的正规式是(14)。
admin
2015-06-03
50
问题
某一确定有限自动机(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和路由器之间传送的数据帧与路
国际标准化组织制定的OSI网络管理协议是(1),另外,ISO还定义了5个管理功能域,(2)属于性能管理域。LAB制定的网络管理协议是SNMP,在SNMPv2管理框架中使用的管理信息库为(3)。管理站(Manager)通过GetRequest命令查询代理(A
在局域网标准中,(31)与FDDI MAC帧格式较为相似。(32)介质访问控制方法对最短帧长度有要求,(33)对传输线路的最短长度有要求。长10km,速率为16Mb/s,100个站点的令牌环,每个站点引入1位延迟位,信号传播速度为200 m/μs,贝该环上
IEEE802.11定义了无线局域网的两种工作模式,其中的(208)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,它通过把一组需要互相通讯的无线网卡的ESSID设为同值来组网。IEEE802.11的物理层规定了三种传输技术,即红外技术、直接
TCP是一个面向连接的协议,它提供连接的功能是(51)的,采用(52)技术来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(53)分组,这种分组的数量最多可为(54),TCP协议采用滑动窗口协议解决了(55)。
下面叙述中正确的是(16)。不是进程调度时机的是(17)。多道程序系统中,当(18)时,进程从执行状态转变为就绪状态。系统中有4个并发进程,都需要某类资源3个。试问该类资源最少为(19)个时,不会因竞争该资源而发生死锁。若P/V操作的信号量S的初值为3,则
某用户无法访问域名为www.cisco.com的网站,在用户主机上执行tracert命令得到提示如下:根据提示信息,造成这种现象的原因可能是__________。
阅读下列说明和C++代码,将应填入()处的字句写在答题纸的对应栏内。【说明】某图像预览程序要求能够查看BMP、JPEG和GIF三种格式的文件,且能够Windows和Linux两种操作系统上运行。程序需具有较好的扩展性以支持新的文件格式和操作系统
结构化开发方法中,数据流图是________阶段产生的成果。
随机试题
"Scienceandeverydaylifecannotandshouldnotbeseparated."ThosewerethewordsutteredbypioneeringBritishscientistRos
下列关于朱砂用法用量和使用注意的叙述,正确的有
90°射频脉冲激发后,组织中将产生宏观横向磁化矢量,射频脉冲关闭后,由于主磁场的不均匀造成了质子群失相位,组织中的宏观横向磁化矢量逐渐衰减。到TE/2时刻,施加一个180。聚相脉冲,质子群逐渐聚相位,组织中宏观横向磁化矢量逐渐增大;到了TE时刻,质子群得以
下列关于城市供电规划的表述,哪项是正确的?()
桥梁支架施工时需对支架进行设计计算,其计算荷载应主要考虑()。
下列关于水泥凝结时间标准说法正确的是()。
下列关于我国民族区域自治制度的表述,不正确的是()。
惠农政策
[2004年MBA真题]国产影片《英雄》显然是前两年最好的古装武打片。这部电影是由著名导演、演员、摄影师、武打设计师和服装设计师参与的一部国际化大制作的电影。票房收入的明显领先说明观看该部影片的人数远多于进口的美国大片《卧虎藏龙》的人数,尽管《卧虎藏龙》也
WillRussiachangetheclocktowintertimethisautumn?
最新回复
(
0
)