大门| 2007大门|问题47

考虑下面的DFA，其中S0是起始状态，S1，S3是最终状态。 DFA能识别什么语言？ （A） x和y的所有字符串 （B） 具有偶数x和偶数y或奇数x和奇数y的x和y的所有字符串 （C） x和y的所有字符串，其x和y的数量相等 （D） 具有偶数x和奇数y或奇数x和偶数y的x和y的所有字符串 答复: （D） 说明： 字母x将从S0状态移动到S1，字母y将从S0状态移动到S3。因此，DFA接受的最小字符串是{x，y}。从S1或S3到接受状态的进一步可能移动可以是偶数长度的x和y的任意组合，即{xx，xy，yx，yy}及其组合中的任一个。因此，DFA接受的语言可以被识别为（x+y）+（xx+xy+yx+yy）*，即所有长度为奇数的x和y字符串（x的偶数和y的奇数或y的偶数和x的奇数）。 选项消除方法：（至少有一个示例不被DFA接受的选项） 选项（A）：错误，因为DFA不接受{xx，xy等}。 选项（B）：错误，因为DFA不接受偶数个x和偶数个y字符串{xxyy}。 选项（C）：False，因为DFA不接受数量相同的x和数量相同的y{xy}的字符串。 选项（D）：接受所有具有偶数x和奇数y或奇数x和偶数y的字符串。 因此，答案是选项（D）。

这个解决方案是由 安田荣彦 这个问题的小测验