2. 计算机
  3. 下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串 ______。

下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串 ______。

admin2021-01-11  29
问题 下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串 ______。
选项 A、bbaa
B、aabb
C、abab
D、baba
答案B
解析 本题考查程序语言基础知识。
有限自动机(确定或非确定的)识别字符串的过程都是从初态出发，找出到达终态的一条路径，使得路径上的字符序列与所识别的字符串相同。
对于bbaa，若路径为s0→s0→s0→s0→s1，则所识别的bbaa结束时s1不是终态；换一条路径s0→s0→s0→s1，此时不存在从s1出发可以识别bbaa中的最后1个a的状态转移，由于不存在其他可能的路径，所以bbaa不能被该自动机识别。
对于aabb，若路径为s0→s0→s0→s0→s0，则字符串aabb结束时s0不是终态；换一条路径s0→s0→s1→s2→s3，所识别的aabb结束时s3是终态，所以aabb可以被该自动机识别。
对于abab，若路径为s0→s0→s0→s0→s0，则所识别的abab结束时s0不是终态；换一条路径s0→s0→s0→s1→s2，则所识别的abab结束时s2不是终态，由于不存在其他可能的路径，所以abab不能被该自动机识别。
对于baba，若路径为s0→s0→s0→s0→s0，则所识别的baba结束时s0不是终态；换一条路径s0→s0→s0→s0→s1，则所识别的baba结束时s1不是终态；再换一条路径s0→s0→s1→s2，此时不存在从s2出发可以识别baba中的最后1个a的状态转移，由于没有其他可能的路径，所以baba不能被该自动机识别。
转载请注明原文地址:https://kaotiyun.com/show/ehPZ777K
本试题收录于： 软件评测师上午基础知识考试题库软考中级分类
0

软件评测师上午基础知识考试

软考中级

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