首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
admin
2005-03-15
136
问题
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
选项
A、(a|b)* bb(a*b*)*
B、(a|b)*bba*|b*
C、(a*b*)bb(a|b)*
D、(a*|b*)*bb(a*|b*)
答案
A
解析
在状态转换图中,每一个结点代表一个状态,其中双圈是终结状态。该题实际上是一个简化确定有限自动机(DFA)的过程,一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。
首先介绍2个概念:最小状态DFA和等价状态。
最小状态DFA必须满足以下2个条件。
(1)没有多余状态(死状态):多余状态从该自动机的开始状态出发,任何输入串都不能到达的那个状态。
(2)没有2个状态是互相等价(不可区别)。
2个状态s和t如果同时满足下列2个条件,就称s和t是等价的。
(1)一致性:同是终态或同是非终态。
(2)蔓延性:从s出发读人某个a和从t出发读入某个a到达的状态等价。
本题的简化过程如下:
首先,将图中状态分为终态和非终态2个子集即({0,1},{2,3}),再进行子集划分,观察第一个子集{0,1},输入b后,状态0转换为状态1,而状态1转换为状态2。因此{1}和{2}中的状态是可区别的。
由于状态2,3输入字符a得到相同的结果3,输入字符b得到相同结果2,所以子集 {2,3}是不可区别的。从而得到新的划分:({0},{1},{2,3}),因此,(2)空的正确答案为B。
重复子集划分步骤,发现新的状态无法再次划分。
所以,本题中2,3状态可以消除3状态,得到新的状态转换图如图3-2所示。
由图3-2可知终态2可以转换为正规表达式(a|b)*,同时必须输入连续2个b字符,才能完成0状态到终态2的转换,所以结果正规表达式必为形如“...bb(a|b)*”的字符串。又因为0和1之间由b和a轮回输入,可以表示为(ba)*,同时,状态0上输入a又回到自身,可以表示为a*。因此,(1)空的正确答案应该为(a*b*)*bb(a|b)*,根据正规式之间的代数性质,(a*b*)*bb(a|b)*与(a|b)*bb(a*b*)*等价。
转载请注明原文地址:https://kaotiyun.com/show/voxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。1.将(1)处空缺设备的名称填写在相应位置。2.(1)所在局域网内的PC或笔记本计算机的IP地址有
请根据图完成R0路由器的配置:R0(config)#interfacesO/O(进入串口配置模式)R0(config—if)#ipaddress202.114.13.1(1)(设置IP地址和掩码)R0(config)#encapsulation
在Linux系统中,DHcP服务默认的配置文件为:(1)。(1)备选答案:A./etc/dhcpd.confB./etc/dhcpd.configC./etc/dhcpc.confD./etc/dhcp.config管理员可
在Linux中,分区分为主分区、扩展分区和逻辑分区,使用fdisk-1命令获得分区信息如下所示:Disk/dev/hda:240heads,63sectors,1940cylindersUnits=cyliridersof1
阅读以下说明,回答以下问题,将解答填入答题纸对应的解答栏内。【说明】某单位网络拓扑结构如下图所示,该单位.Rotlter以太网接口E0接内部交换机S1,S0接口连接到电信ISP的路由器;交换机S1连接内部的Web服务器、DHCP服务器、
Packet-switching wireless networks are preferable(66)when transmissions are(67)because of the way charges are(68)per packet. Cir
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
SDLC was invented by IBM to replace the older Bisynchronous protocol for wide area connections between IBM equipment. A varietio
随机试题
清化热痰,除烦止呕的药物是清热除烦,生津利尿的药物是
既能行气止痛,叉能健脾消食的药物是()
(2010)医院洁净手术部内与室内空气直接接触的外露材料不得使用()。
下列物质中酸性最弱的是()。
根据《建设项目工程总承包合同示范文本(试行)》,下列关于预付款保函和预付款支付的说法,正确的是()。
某医院的扩建工程,总建筑面积2.6万m2,其中地下两层,1.4万m2,设有专门用于肿瘤治疗的特种医疗设施设备和停车库。该工程施工总承包单位中标后,为确保施工进度计划能得以实施,编制的计划有()。
做忠诚的爱国者,应当
在VBA中要打开名为“学生信息录入”的窗体,应使用的语句是()。
ItwasacoldspringmorninginLondon.Peoplewalkinginthestreetwerewearingheavyclothes.Theweatherhadbeenverybadf
A、TakeNo.232bus.B、Youcangothere.C、It’salongwaytogo.D、Itdoesn’tmatter.A
最新回复
(
0
)