algorithm - if (A⋂B)⋃(B⋂C) 是否为空的可判定性

Question

我一直在试图解决 CFG 的可判定性问题，我只是想问一下我解决这个问题的方法（标题）是否准确。

根据我的理解：如果 A、B、C 是CFL，那么 A⋂B 和 B⋂C 在交集下不是封闭的，因此确定它们是否为空在算法上是无法确定的，因为交集不一定是 CFL。
因此，对于确定 (A⋂B)⋃(B⋂C) 是否为空的算法，它需要能够根据联合的定义评估 (A⋂B) 和 (B⋂C) 是否为空。但是由于 CFL 交集的空性问题是不可判定的，所以 (A⋂B)⋃(B⋂C) 的空性问题也应该是不可判定的。

我的逻辑正确吗？任何帮助我理解这一点的解释都非常感谢。

标签： algorithmautomationcontext-free-grammarformal-languagescontext-free-language