GATE 2008 论文中提出了以下问题:
如果 L 和 L' (L 补码)是递归可枚举的,那么 L 是 ?
a) 常规
b) CFL
c) CSL
d) 递归
正确的选项是选项 (d),我接受这是真的。但我的问题是为什么不能是常规的或 CSL ?
因为我认为如果我们认为L是正则的,那么L'也是正则的(因为正则语言在互补下是封闭的)。现在因为L'是规则的,所以根据'乔姆斯基层次结构' L'也是递归可枚举的。即使L在常规之后,它也适合问题陈述,那么为什么选项(a)不是正确的选项?CSL 也是如此,那么为什么选项 (c) 也不是正确的选项?