in Theory of Computation
404 views
0 votes
0 votes
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
in Theory of Computation
by
404 views

1 comment

For any string of a given CFG, Number of Left most Derivations = Number of right most derivations = Number of parse trees.
2
2

1 Answer

4 votes
4 votes
For any unambiguous grammar,

LMD and RMD is same and we have only 1 parse tree. Therefore LMD = RMD = #Parse tree

For ambiguous grammar,

LMD = RMD <= #Parse tree
edited by

4 Comments

For a grammar, it’s true that if every string has only 1 parse tree then it’s unambiguous. But, I’m asking for an aribitrary string in that grammar. It may still happen that some string has only 1 parse tree in an ambiguous grammar, right?

0
0

@atulcse For an unambiguous grammar every string produced by it will have 1 parse tree. But for a given string many grammars may produce it and some of them can be ambiguous too. If that grammar is ambiguous so there will exist more than 1 parse tree for that given string according to that ambiguous grammar production rules.

3
3

A grammar is ambiguous if either 2 or more parse trees/ 2 or more LMD / 2 or more RMD can be made for that grammar. So @adad20 you are right. 

For a given string and some ambiguous grammar producing it,  is #LMD = #RMD always true?

I don’t know about any such relations :(

May refer this, though not sure : https://gateoverflow.in/168440/Derivations 

2
2

Related questions