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

admin2019-05-11 13

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

选项 A、bbaa
B、aabb
C、abab
D、baba

答案B

解析本题考查程序语言基础知识。
有限自动机(确定或非确定的)识别字符串的过程都是从初态出发，找出到达终态的一条路径，使得路径上的字符序列与所识别的字符串相同。
对于bbaa，若路径为sO-＞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/C5VZ777K

本试题收录于：程序员上午基础知识考试题库软考初级分类

0

程序员上午基础知识考试

软考初级

相关试题推荐

随机试题

最新回复(0)