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

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

admin2021-01-13  32
问题 某非确定的有限自动机(NFA)的状态转换图如下图所示(q0既是初态也是终态)。以下关于该NFA的叙述中，正确的是____________。
选项 A、其可识别的0、1序列的长度为偶数
B、其可识别的0、1序列中0与1的个数相同
C、其可识别的非空0、1序列中开头和结尾字符都是0
D、其可识别的非空0、1序列中结尾字符是1
答案D
解析 本题考查程序语言基础知识。
    若存在一条从初态到某一终止状态的路径，且这条路径上所有弧的标记符连接成的字符串等于(ω，则称ω可由NFA识别(接受或读出)。
    对于题中给出的NFA，其初态为q0，q0上的自回路表示识别零个或多个1，接下来识别出一个0时进入状态q1，q1上的自回路表示识别零个或多个0，接下来识别出1个1之后再回到q0。
    例如，该自动机可识别空串(因为q0既是初态，也是终态)、01、00001、101、l、11、111、1111等。
    01的识别路径为q0－＞q1－＞q0
    00001的识别路径为q0－＞q1－＞q1－＞q1－＞q1－＞q0  
    101的识别路径为q0－＞q0－＞q1－＞q0
    1的识别路径为q0－＞q0
    11的识别路径为q0－＞q0－＞q0
    111的识别路径为q0－＞q0－＞q0－＞q0
    1111的识别路径为q0－＞q0－＞q0－＞q0－＞q0
    识别字符串时必须从初始状态q0出发，并回到状态q0，因此对于仅由1构成的任意长度的串，在识别过程中不会离开q0。当识别出一个0而离开q0后就进入q1，此后的字符若全部为0，则会一直在q1，直到识别出一个1而回到q0，因此除了空串，该NFA识别的字符串必须以1结尾。
转载请注明原文地址:https://jikaoti.com/ti/tdG7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

相关试题推荐
随机试题
最新回复(0)