context-free-grammar - 有什么算法可以解决 CFG 的歧义？

Question

这是一个模棱两可的CFG：

S -> aSb|bA|Ba
A -> bA|B
B -> aB|A|ε

您可以通过解析字符串“ba”轻松检查语法的歧义。

是否有任何算法可以解决上述 CFG 的歧义？

谢谢您的帮助

Answer 1

检查语法是否模棱两可是一个不可判定的问题，这意味着不存在每次都能正确输出是/否的算法。

不可判定性通过证明它等同于 Post Correspondence Problem 来显示，后者也是不可判定的。