首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
admin
2005-03-15
108
问题
如图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
X.25规范对应OSI参考模型中的3层,X.25的第3层描述了分组的格式及分组交换的过程。X.25的第2层由LAPB(LinkAccessProcedure,Balanced)实现,它定义了用于DTE/DCE连接的帧格式。X.25的第1层定义了电气和
阅读以下说明,回答问题1~4,将解答填入对应栏内。A公司用一台Web服务器和一台应用服务器来管理销售信息。销售人员在办公室时通过PC机来访问应用服务器,若在公司以外,则通过移动电话或PDA(PersonalDigitalAssistant)访问公司网
阅读以下说明,回答问题1~7,将解答填入对应的解答栏内。图3-1是在网络中划分VLAN的连接示意图。VLAN可以不考虑用户的物理位置,而根据功能、应用等因素将用户从逻辑上划分为一个个功能相对独立的工作组,每个用户主机都连接在支持VLAN的交换机端口
阅读以下说明,回答问题1~7,将解答填入对应的解答栏内。图3-1是在网络中划分VLAN的连接示意图。VLAN可以不考虑用户的物理位置,而根据功能、应用等因素将用户从逻辑上划分为一个个功能相对独立的工作组,每个用户主机都连接在支持VLAN的交换机端口
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
阅读以下说明,回答问题,将解答填入答题纸对应的解答栏内。【说明】图2-1为某公司数据中心拓扑图,两台存储设备用于存储关系型数据库的结构化数据和文档、音视频等非结构化文档,规划采用的RAID组合方式如图2-2、图2-3所示。图2-2所示的RAID方
以太网中如果发生介质访问冲突,按照二进制指数后退算法决定下一次重发的时间,使用二进制指数后退算法的理由是(56)。
如果两个交换机之间设置多条Trunk,则需要用不同的端口权值或路径费用来进行负载均衡。默认情况下,端口的权值是(55)。在如下图所示的配置下,(56)。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(58);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(59)。(59)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
随机试题
高效液相色谱法用于含量测定时,对系统性能的要求
刚体作平动时,某瞬时体内各点的速度与加速度为:
()的主要投资对象是资本市场上的上市股票与债券,货币市场上的短期票据与银行同业拆借,以及金融期货、黄金、期权交易、不动产等。
根据现行国家工程建设消防技术标准的要求,下列供暖系统的设置不符合相关规定的是()。
居民乙因拖欠居民甲180万元款项无力偿还,2010年6月经当地有关部门调解,以房产抵偿该笔债务,居民甲因此取得该房产的产权并支付给居民乙差价款20万元。假定当地省政府规定的契税税率为5%。下列表述中正确的是()。(2010年)
阅读下列材料:为了让高中一年级学生能够完整地体验信息处理的全过程,教师通常会设计一个综合性的主题学习活动。“我的悠长假期”主题学习活动即以图像处理为栽体,让学生体验信息采集、加工与表达的全过程。下面是本次主题活动方案:活动目的:以图片处理为载体体验信息
“三弦”这种乐器属于民族乐器中的()类。
元认知指的是对认知的认知,即认知主体关于自己认知过程的知识和调节这些过程的能力,对思维和学习活动的知识和控制。元认知的实质是对认知活动的自我意识和自我调节。根据上述定义,以下包含元认知的是()。
DerVatergibt______TochterdenWagen.
I_______thepicturefromthewallinordertocleanit.
最新回复
(
0
)