GATE | GATE-CS-2006 |问题33

设L1为常规语言，L2为确定性上下文无关语言，L3为递归可枚举但非递归语言。以下哪项陈述是错误的？ （A） L1∩ L2是确定性CFL （B） L3∩ L1是递归的 （C） L1∪ 二语是上下文无关的 （D） L1∩ L2∩ L3是递归可枚举的 答复: （B） 说明： （A） 这种说法是正确的，因为确定性上下文无关语言在与常规语言相交时是封闭的。 （B） 这个语句是错误的，因为L1是递归的，并且每种递归语言都是可判定的。L3是递归可枚举的，但不是递归的。所以，L3是不可判定的。递归语言和递归可枚举语言的交集是递归可枚举的。 （C） 这句话是真的，因为L1是正则的。每种常规语言也是一种上下文无关的语言。L2是一种确定性的上下文无关语言，每一种DCFL也是一种上下文无关语言。每一种与上下文无关的语言都在联合之下是封闭的。 （D） 这个语句是真的，因为L1是正则的，所以它也是递归可枚举的。L2是确定性上下文无关语言，因此，它也是递归可枚举的。递归可枚举语言在交集下是封闭的。

因此，选项（A）中提到的问题是无法确定的。 如果你在上面的帖子中发现任何错误，请在下面发表评论。 这个问题的小测验