algorithm - 递归可枚举语言的闭包属性

Question

请考虑以下问题：

让L1和L2成为两种语言。证明或证伪下 re 语言类的封闭性

1. 区别(L1 - L2)

2. 产品(L1 x L2) （尝试在已知的假设下证明产品，其中单词L1结束以及不知道的情况。

在这里，封闭性意味着如果L1并且L2可以被旅行机器接受，那么也(L1 - L2)或(L1 x L2)

笔记

我能够找出联合和补充的解决方案（联合：封闭；补充：不封闭），但不适用于上述（差异或产品）。

Answer 1

1) RE 在差值下不闭合。

证明：假设是。

设Sigma为任意 RE 语言的字母表L。Sigma^*是 RE（TM 只检查输入字符串是否仅包含符号 fromSigma或为空）。如果 RE 将在差异下关闭，尤其Sigma^* - L是 RE。但是任何 RE 语言都是递归的（可判定的）。但是，存在无法确定的 RE 语言（参见停止问题）。

2) RE 在笛卡尔积下闭合

证明草图：首先假设一个 oracle 将输入字符串正确划分为来自L1,的单词L2。T1在这种情况下，运行 TMsT2以依次检查其输入的L1、 、L2、 resp. 中的包含情况。如果两个 TM 都终止，则此设置终止。

接下来假设没有神谕。对于任何给定的输入 string w，都有 length(w)+1可能的分区。在来自相应分区的输入上并行运行length(w)+1连接的 TM 的副本，T1每个T2分区一个副本。如果至少有一个克隆的 TM 连接终止，则此设置终止，这相当于输入字符串部分是L1, L2, resp 的成员。