2. 计算机
  3. 下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别( )。

下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别( )。

admin2019-05-11  37
问题 下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别(  )。
选项 A、abab
B、aaaa
C、babb
D、abba
答案A
解析 要判断一个字符串能否被指定的自动机识别，就看在该自动机的状态图中能否找到一条从开始状态到终止状态的路径，且路径上的字符串等于要识别的字符串。对于字符串“abab”，识别路径为s0→s1→s2→s1→s2，字符串结束时的状态不是终止状态，所以该自动机不能识别“abab”。字符串“aaaa”的识别路径为s0→s1→s3→s3→s3，字符串“babb”的识别路径为s0→s2→s1→s2→s3，字符串“abba”的识别路径为s0→sl→s2→s3→s3，它们结束时的状态都是终止状态，所以都能被自动机识别。
转载请注明原文地址:https://kaotiyun.com/show/YMVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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