Search code examples
context-free-grammarautomataautomata-theory

Any algorithm to fix the ambiguity of a CFG?

Here is an ambiguous CFG:

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

You can easily check the ambiguity of the grammar by parsing the string "ba".

Are there any algorithms to fix the ambiguity of a CFG like the one above?

Thanks for the help

Solution

  • 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.