GATE 2008 论文中提出了以下问题：
如果 L 和 L' （L 补码）是递归可枚举的，那么 L 是 ?
a) 常规
b) CFL
c) CSL
d) 递归
正确的选项是选项 (d)，我接受这是真的。但我的问题是为什么不能是常规的或 CSL ？
因为我认为如果我们认为L是正则的，那么L'也是正则的（因为正则语言在互补下是封闭的）。现在因为L'是规则的，所以根据'乔姆斯基层次结构' L'也是递归可枚举的。即使L在常规之后，它也适合问题陈述，那么为什么选项（a）不是正确的选项？CSL 也是如此，那么为什么选项 (c) 也不是正确的选项？
快速回顾一下语言类——我们知道这 5 个语言类都是（严格）彼此的子集：
常规 ⊂ CFL ⊂ CSL ⊂ 递归 ⊂ 递归可枚举
问题是，如果我们知道语言 L 是递归可枚举的，并且我们知道它的补码 L' 也是递归可枚举的，那么我们能确定 L 属于哪个更小的类？
答案等同于说，如果语言 L 是递归可枚举而不是递归的，那么 L' 不是递归可枚举的。该陈述是正确的，但任何其他语言类的等效陈述都不是。
如果 L 和 L' 都是递归可枚举的，那么
a) L 可能是正则的（事实上，如果 L 是正则的，那么 L' 也是正则的，并且所有正则语言都是递归可枚举的）......但是有些非正则语言的补码是递归可枚举的
b) L 可能是 CFL（有些 CFL 的补码也是 CFL，也有 CFL 的补码不是 CFL）......但是有些非上下文无关语言的补码是递归可枚举的
c) L 可能是一个 CSL（有些 CSL 的补码是 CSL）......但是有些非上下文敏感语言的补码是递归可枚举的
d) L 必须是递归的，因为由于 L 和 L' 都是递归可枚举的，我们有一个有效的可计算过程来确定任何给定的字符串是否在 L 中：开始枚举每种语言中的字符串，交叉枚举（所以你给出 L 中的下一个字符串，然后是 L' 中的下一个字符串，然后返回 L，等等）。继续这个过程最终会在 L 或 L' 中找到目标字符串，此时您可以返回 true（如果它在 L 中枚举）或 false（如果在 L' 中枚举）。
因此，虽然 L可以是常规的、CFL 或 CSL 是正确的，但它可能不是其中的任何一个也是正确的；但它必须绝对是递归的。因此，这是“最佳”答案，也是唯一在所有情况下通常都是正确的答案。