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

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









