递归可枚举集和图灵机
Recursively enumerable sets and Turing machines
令 L1 为递归语言。设 L2 和 L3 是可递归枚举但不可递归的语言。以下哪项陈述不一定正确？ (A) L2 – L1 是递归可枚举的。 (B) L1 – L3 是递归可枚举的 (C) L2 ∩ L1 是递归可枚举的 (D) L2 ∪ L1 是递归可枚举的
你没看错，答案是（B）。您应该找到 L1（一种递归语言）和 L3（一种 RE 语言）的具体示例，其中 L1- L3 不是 RE.
以下是陈述 (A)、(C) 和 (D) 成立的证明。我使用的事实是 every recursive language is recursively enumerable, and the well-known closure properties of RE languages.
(A) L2 - L1 = L2 intersection (complement L1) 是递归可枚举的，因为 L1 是递归的，因此 (complement L1) 是递归可枚举的，RE 语言的交集又是 RE 语言。 （一般来说，RE 语言 L 的补码是 RE 当且仅当 L 是递归的。）
(B) L1 - L3 = L1 交集（补 L3） 不必是 RE。 （练习：找到一个反例，即找到具体的语言 L1（递归）和 L3（RE）使得 L1- L3 不是 RE.)
(C) L2 交集 L1 是 RE 因为 L1 和 L2 都是 RE我们知道两种 RE 语言的交集又是一种 RE 语言。
(D) L2 union L1 是 RE 因为 L1 和 L2 都是 RE我们知道两种 RE 语言的联合也是一种 RE 语言。
L1-L3=L1 交点不必是 RE
你没看错，答案是（B）。您应该找到 L1（一种递归语言）和 L3（一种 RE 语言）的具体示例，其中 L1-L3 不是 RE。
答案是B.you应该找到L1和L3的具体例子
令 L1 为递归语言。设 L2 和 L3 是可递归枚举但不可递归的语言。以下哪项陈述不一定正确？ (A) L2 – L1 是递归可枚举的。 (B) L1 – L3 是递归可枚举的 (C) L2 ∩ L1 是递归可枚举的 (D) L2 ∪ L1 是递归可枚举的
你没看错，答案是（B）。您应该找到 L1（一种递归语言）和 L3（一种 RE 语言）的具体示例，其中 L1- L3 不是 RE.
以下是陈述 (A)、(C) 和 (D) 成立的证明。我使用的事实是 every recursive language is recursively enumerable, and the well-known closure properties of RE languages.
(A) L2 - L1 = L2 intersection (complement L1) 是递归可枚举的，因为 L1 是递归的，因此 (complement L1) 是递归可枚举的，RE 语言的交集又是 RE 语言。 （一般来说，RE 语言 L 的补码是 RE 当且仅当 L 是递归的。）
(B) L1 - L3 = L1 交集（补 L3） 不必是 RE。 （练习：找到一个反例，即找到具体的语言 L1（递归）和 L3（RE）使得 L1- L3 不是 RE.)
(C) L2 交集 L1 是 RE 因为 L1 和 L2 都是 RE我们知道两种 RE 语言的交集又是一种 RE 语言。
(D) L2 union L1 是 RE 因为 L1 和 L2 都是 RE我们知道两种 RE 语言的联合也是一种 RE 语言。
L1-L3=L1 交点不必是 RE
你没看错，答案是（B）。您应该找到 L1（一种递归语言）和 L3（一种 RE 语言）的具体示例，其中 L1-L3 不是 RE。
答案是B.you应该找到L1和L3的具体例子