某一确定性有限自动机(DFA)的状态转换如图2-4所示，则以下字符串中，不能被该DFA接受的是(18)。 ①0010 ②0001 ③0101

admin2015-06-03 43

问题某一确定性有限自动机(DFA)的状态转换如图2-4所示，则以下字符串中，不能被该DFA接受的是(18)。
①0010
②0001
③0101

选项 A、①，②
B、①，③
C、②，③
D、①，②，③

答案C

解析本题主要考查有限自动机识别字符串，这也是考试中一个常考的知识点。所谓被有限自动机所识别，就是依次输入字符串中的字符，判断其是否能使有限自动机从初态开始到终态结束，如果能，则能被该有限自动机所识别，反之，则视为不能被该有限自动机所识别。
在本题中，给出了3个字符串，分别来判断这3个字符串是否能别有限自动机所识别。
对于字符串0010，从初态q0出发，输入0后，跳转到自己，然后再输入0，依然调整到自己，然后输入1，跳转到终态q₁，这个时候要注意，看到这里很多考生就认为该字符串能被该有限自动机所识别，但其实不然，因为还有一个字符0没有输入，如果输入这个0，则又跳转到了初态，因此该字符串不能被有限自动机所识别。
对于字符串0001，从初态q₀出发，输入3个0后，仍然跳转到自己，然后再输入1，跳转到终态q₁，这时，字符串中的字符已经输入完成，因此该字符串能被该有限自动机所识别。
对于字符串0101，从初态q₀出发，输入后，跳转到自己，然后再输入1，跳转到终态q₁，输入字符0，又跳转到初态q₀，再输入1，跳转到终态q₁，因此在字符串输入完成后，自动机的状态停在终态，所以该字符串同样能被本题的有限自动机所识别。

转载请注明原文地址:https://kaotiyun.com/show/HCRZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

某一确定性有限自动机(DFA)的状态转换如图2-4所示，则以下字符串中，不能被该DFA接受的是(18)。 ①0010 ②0001 ③0101

软件设计师上午基础知识考试

软考中级

Internet是由众多网络互联而成的计算机网络，狭义Internet是指由那些采用IP协议的网络互联而成的网络，广义Internet是指狭义Internet加上所有(332)的网络。Internet体系结构具有良好扩充性的主要原因在于它(333)。广义I

为了进行差错控制，在局域网中对数据帧广泛使用的校验方法是(178)校验。CRC-16规定的生成多项式为G(x)=X16+X15+X2+1，它产生(179)位的校验码，当接收端发现错误后会(180)。如果CRC的生成多项式为G(X)=X4+X+1，码字为10

下面关于二级目录的叙述中，错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题，通常在文件系统中采用(5)。

以下关于钓鱼网站的说法中，错误的是()。

社会主义初级阶段基本路线的简明概括和主要内容是

首选用于治疗肺炎气阴两伤，余热未尽证(正虚邪恋证)的方剂是()

A．针对所用药物或出现意外情况，建议采取相应措施B．使患者用药后迅速达到预期目的C．药物的使用时间应尽量缩短D．控制医疗保健费用的过度增长E．药物的使用方法便于医生和患者掌握

下列关于估值的基本原则，说法错误的是()。

下列关于运动性猝死的描述正确的是()。

下列句子中标点符号使用正确的一项是()。

主体是指具有思维能力、从事社会实践和认识活动的人；客体是指实践和认识活动所指向的对象。马克思主义认识论认为，主体与客体关系的内涵包括

设un(x)满足u’n(x)=un(x)+xn—1ex(n=1，2，…)，且un(1)=un(x)的和函数．

TheOscarEveryspring,themovieindustrygearsupforitsbiggestcelebration:theAcademyAwards,morecommonlyknownas

某一确定性有限自动机(DFA)的状态转换如图2-4所示，则以下字符串中，不能被该DFA接受的是(18)。 ①0010 ②0001 ③0101

软件设计师上午基础知识考试

软考中级

Internet是由众多网络互联而成的计算机网络，狭义Internet是指由那些采用IP协议的网络互联而成的网络，广义Internet是指狭义Internet加上所有(332)的网络。Internet体系结构具有良好扩充性的主要原因在于它(333)。广义I

为了进行差错控制，在局域网中对数据帧广泛使用的校验方法是(178)校验。CRC-16规定的生成多项式为G(x)=X16+X15+X2+1，它产生(179)位的校验码，当接收端发现错误后会(180)。如果CRC的生成多项式为G(X)=X4+X+1，码字为10

下面关于二级目录的叙述中，错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题，通常在文件系统中采用(5)。

以下关于钓鱼网站的说法中，错误的是()。

已知一个NFA M图如下所示，采用子集构造法将其确定化为DFA的过程如下表所示。 表中的状态集合T

社会主义初级阶段基本路线的简明概括和主要内容是

首选用于治疗肺炎气阴两伤，余热未尽证(正虚邪恋证)的方剂是()

A．针对所用药物或出现意外情况，建议采取相应措施B．使患者用药后迅速达到预期目的C．药物的使用时间应尽量缩短D．控制医疗保健费用的过度增长E．药物的使用方法便于医生和患者掌握

下列关于估值的基本原则，说法错误的是()。

下列关于运动性猝死的描述正确的是()。

下列句子中标点符号使用正确的一项是()。

主体是指具有思维能力、从事社会实践和认识活动的人；客体是指实践和认识活动所指向的对象。马克思主义认识论认为，主体与客体关系的内涵包括

设un(x)满足u’n(x)=un(x)+xn—1ex(n=1，2，…)，且un(1)=un(x)的和函数．

TheOscarEveryspring,themovieindustrygearsupforitsbiggestcelebration:theAcademyAwards,morecommonlyknownas