471 views
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?

### 1 comment

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

For any unambiguous grammar,

#LMD = #RMD = #Parse tree = 1

For ambiguous grammar,

#LMD = #RMD <= #Parse tree
by

for ambiguous grammars, will lmd + rmd >= #pt be more accurate? since the question says "for a given string", it may be possible that the given string has lmd = rmd and only one parse tree but the CFG itself is ambiguous.

edited by

Grammar is ambiguous if it has more than one RMD or more than one LMD and each LMD or RMD corresponds to a parse tree.

If a grammar has 1 LMD and 1 RMD its parse tree will be same and the language is not ambiguous.

I have a doubt here

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

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?

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

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

bro one more thing I want to to add
if I say
Unambigous grammer has same LMD and RMD  , it is false
it can be but for unambigous grammer parse tree should be same.

1 vote