436 views
0 votes
0 votes
Could anyone please explain various tricks to find out wheather the given context free Grammar is ambiguous or not in an easier way?

2 Answers

5 votes
5 votes

It’s an Undecidable problem, so no algorithm exists. (This is because it can be shown that this problem is equivalent to Post Correspondence Problem which is an Undecidable problem)

Now you can try to generate some strings from the grammar and check if there exists at least one string for which more than one parse tree exists( or more than one leftmost derivation exist or more than one rightmost derivation exist) then the CFG is Ambiguous.

If a CFG (without useless symbols) is both left-recursive and right-recursive for the same non-terminal then that CFG is ambiguous. But the converse is false (means an ambiguous CFG may not have both left and right recursion).

CFG = Context-Free-Grammar.

Good read: Ambiguous grammar - Wikipedia

If anyone wants to add something more please comment.

edited by
0 votes
0 votes

@vishnu777

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree...

If a context free grammar G has more than one derivation tree for some string w ∈ L(G), it is called an ambiguous grammar...

There exist multiple right-most or left-most derivations for some string generated from that grammar....

 

1. https://gateoverflow.in/10736/Inherently-ambiguous-grammar 

 

2. https://gateoverflow.in/92710/Decidability?show=92715#a92715 

 

3. https://gateoverflow.in/113207/Re-or-non-re

 

No related questions found