context-free-grammar - CFG 和 DCFG 可判定问题

Question

你们能否列出您所知道的可判定为无上下文语言和确定性无上下文语言的问题。我确实在 Stack Overflow 和 Wiki 上获得了一些关于不可判定问题列表的信息，但与 CFG 或 DCFG 等细节无关。这个问题列表（带有证明/链接）可能对寻找此类问题的人非常有帮助。

Answer 1

与 DCFG 和 CFG 相关的一个非常有趣的可判定问题是。我们可以比较两个 DCFG (DPDA)，但我们不能比较两个 CFG。DPDA(DCFG)的等价问题已被证明是可判定的。[链接]（http://www.lfcs.inf.ed.ac.uk/reports/99/ECS-LFCS-99-411/ECS-LFCS-99-411.pdf）在本文档中有很好的解释。