1

GATE 2008 论文中提出了以下问题:

如果 L 和 L' (L 补码)是递归可枚举的,那么 L 是 ?

a) 常规
b) CFL
c) CSL
d) 递归

正确的选项是选项 (d),我接受这是真的。但我的问题是为什么不能是常规的或 CSL ?

因为我认为如果我们认为L是正则的,那么L'也是正则的(因为正则语言在互补下是封闭的)。现在因为L'是规则的,所以根据'乔姆斯基层次结构' L'也是递归可枚举的。即使L在常规之后,它也适合问题陈述,那么为什么选项(a)不是正确的选项?CSL 也是如此,那么为什么选项 (c) 也不是正确的选项?

4

2 回答 2

0

快速回顾一下语言类——我们知道这 5 个语言类都是(严格)彼此的子集:

常规 ⊂ CFL ⊂ CSL ⊂ 递归 ⊂ 递归可枚举

问题是,如果我们知道语言 L 是递归可枚举的,并且我们知道它的补码 L' 也是递归可枚举的,那么我们能确定 L 属于哪个更小的类?

答案等同于说,如果语言 L 是递归可枚举而不是递归的,那么 L' 不是递归可枚举的。该陈述是正确的,但任何其他语言类的等效陈述都不是。

于 2020-09-30T16:18:23.683 回答
0

如果 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 是正确的,但它可能不是其中的任何一个也是正确的;但它必须绝对是递归的。因此,这是“最佳”答案,也是唯一在所有情况下通常都是正确的答案。

于 2020-11-13T19:58:15.963 回答