登机门|登机门CS 2008 |问题48

以下哪项陈述是错误的？ （A） 每个NFA都可以转换为等效的DFA （B） 每个非确定性图灵机都可以转化为等价的确定性图灵机 （C） 每种常规语言也是一种上下文无关的语言 （D） 递归可枚举集的每个子集都是递归的 答复: （D） 说明： 如果存在一个图灵机，它接受该语言的每个字符串，但不接受该语言中不存在的字符串，则该语言是递归可枚举的。 不在语言中的字符串可能会被拒绝，或者可能会导致图灵机进入无限循环。 递归语言不能进入无限循环，它必须明确拒绝字符串，但递归可枚举语言可以进入无限循环。 所以，每种递归语言都是递归可枚举的。 因此，“递归可枚举集的每个子集都是递归的”语句是错误的。 因此，选项（D）就是答案。 如果你在上面的帖子中发现任何错误，请在下面发表评论。 这个问题的小测验