context-free-grammar - CFG のあいまいさを修正するアルゴリズムはありますか?

Question

以下はあいまいな CFG です。

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

文字列「ba」を解析することで、文法のあいまいさを簡単に確認できます。

上記のような CFG のあいまいさを修正するアルゴリズムはありますか?

助けてくれてありがとう

Answer 1

Checking whether a grammar is ambiguous or not is an Undecidable problem, which means that there exists no algorithm which will correctly output Yes/No to this problem every time.

The undecidablity is shown by showing that it is equivalen to Post Correspondence Problem, which is also undecidable.