某非确定的有限自动机(NFA)的状态转换图如下图所示(q0既是初态也是终态)。以下关于该NFA的叙述中，正确的是____________。

admin2021-01-13 36

问题某非确定的有限自动机(NFA)的状态转换图如下图所示(q₀既是初态也是终态)。以下关于该NFA的叙述中，正确的是____________。

选项 A、其可识别的0、1序列的长度为偶数
B、其可识别的0、1序列中0与1的个数相同
C、其可识别的非空0、1序列中开头和结尾字符都是0
D、其可识别的非空0、1序列中结尾字符是1

答案D

解析本题考查程序语言基础知识。
若存在一条从初态到某一终止状态的路径，且这条路径上所有弧的标记符连接成的字符串等于(ω，则称ω可由NFA识别(接受或读出)。
对于题中给出的NFA，其初态为q₀，q₀上的自回路表示识别零个或多个1，接下来识别出一个0时进入状态q₁，q₁上的自回路表示识别零个或多个0，接下来识别出1个1之后再回到q₀。
例如，该自动机可识别空串(因为q₀既是初态，也是终态)、01、00001、101、l、11、111、1111等。
01的识别路径为q₀－＞q₁－＞q₀
00001的识别路径为q₀－＞q₁－＞q₁－＞q₁－＞q₁－＞q₀
101的识别路径为q₀－＞q₀－＞q₁－＞q₀
1的识别路径为q₀－＞q₀
11的识别路径为q₀－＞q₀－＞q₀
111的识别路径为q₀－＞q₀－＞q₀－＞q₀
1111的识别路径为q₀－＞q₀－＞q₀－＞q₀－＞q₀
识别字符串时必须从初始状态q₀出发，并回到状态q₀，因此对于仅由1构成的任意长度的串，在识别过程中不会离开q₀。当识别出一个0而离开q₀后就进入q₁，此后的字符若全部为0，则会一直在q₁，直到识别出一个1而回到q₀，因此除了空串，该NFA识别的字符串必须以1结尾。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

某非确定的有限自动机(NFA)的状态转换图如下图所示(q0既是初态也是终态)。以下关于该NFA的叙述中，正确的是____________。

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

软考中级

在UML提供的图中，(31)用于描述系统与外部系统及用户之间的交互；(32)用于按时间顺序描述对象间的交互。

采用UML进行软件建模过程中，类图是系统的一种静态视图，用(19)可明确表示两类事物之间存在的整体/部分形式的关联关系。

在一棵二叉树的二叉链表中，空指针数等于非空指针数加(55)。

A．牙齿萌出迟缓，乳牙滞留，牙列发育不良，釉质基质形成及钙化受阻B．佝偻病C．唇炎、口角炎、舌乳头肥厚或裂底，牙齿、颌面生长停滞D．水痘E．坏血病维生素A缺乏可引起

某风景名胜区需建设采暖锅炉。锅炉燃料为天然气，经估算模式计算，其排放污染物最大地面质量浓度占标率(Pmax)为8．0％。根据《环境影响评价技术导则一大气环境》，该项目的大气环境影响评价工作等级为()。

某企业本月期初库存材料为8000000元，材料成本差异账户借方余额500000元。本月2日发出委托加工材料的计划成本为800000元，月内收回的加工材料计划成本1000000元，实际成本1020400元；本月购入材料的实际成本2100000元，计划成本20

组织外部环境的具体环境不包括()。

(2014·湖南)教育形成自己相对独立形态的标志是()

人民代表大会是我国立法机关和国家权力机关。()

如图所示，梯形ABCD的对角线AC上BD，其中AD=1/2，BC=3，AC=14/5，BD=2．1。问梯形ABCD的高AE的值是：

Readthearticlebelowaboutcareersinchildren’sbookpublishingandthequestionsontheoppositepage.Foreachquestion

AreweatthebeginningofanotherAgeofExploration?Perhapsevenmoreimportant,areweatthebeginningof【C1】______AgeofC

Whenwasthefirstactualradiobroadcastmade?