GATE 2008论文中提出了以下问题：
如果L和L'(L补码(是递归可枚举的，那么L是？
a( 常规
b(CFL
c(CSL
d(递归
正确的选项是选项(d(，我承认这是真的但我的问题是，为什么不能是常规赛或中超联赛
因为我认为如果我们认为L是正则的，那么L’也是正则的(因为正则语言在互补下是闭的(。现在，由于L'是正则的，因此根据"Chomsky层次结构"，L'是递归枚举的。即使L是正则的，它也符合问题陈述，那么为什么选项(a(不是正确的选项？CSL也是如此，那么为什么选项(c(也不是一个正确的选项呢？
快速回顾语言类——我们知道这5个语言类都是彼此的(严格(子集：
正则CFL递归可枚举
问题是，如果我们知道一种语言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，但它也可能不是其中的任何一个；但它绝对是递归的。因此，这就是"；最好的"；答案，也是唯一一个在所有情况下都是正确的答案。