证明函数的不可判定性（使用 empty/non-empty 交集）

Question

我必须证明我的函数是不可判定的（在归约中使用 empty/non-empty 交集）。

我的函数是：L(G1) = L(G2) = infinite ^ L(G1) ∩ L(G2) /= infinite

我正在考虑如何证明它。该定理说，无论两个 CFG 的交集是否为空，都是不可判定的。但是在我的情况下，无限的两个集合的交集怎么可能不是无限的，这就是与定理的关系。

Answer 1

假设E是所有偶数的集合，O是所有奇数的集合，F是某个有限的整数集。取 L₁ = E ∪ F 和 L₂ = O ∪ F。显然，L₁ 和L₂都是无穷大，L₁∩L₂是F，是有限的

这也可能对您问题的第二部分有所帮助。