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? Theory of Computation context-free-language theory-of-computation compiler-design finite-automata + – atulcse asked Jan 21, 2022 atulcse 833 views answer comment Share Follow See 1 comment See all 1 1 comment reply Isha_99 commented Jan 21, 2022 reply Follow Share For any string of a given CFG, Number of Left most Derivations = Number of right most derivations = Number of parse trees. 2 votes 2 votes Please log in or register to add a comment.
4 votes 4 votes For any unambiguous grammar, #LMD = #RMD = #Parse tree = 1 For ambiguous grammar, #LMD = #RMD <= #Parse tree Shoto answered Jan 21, 2022 edited Dec 28, 2022 by Shoto Shoto comment Share Follow See all 6 Comments See all 6 6 Comments reply atulcse commented Jan 21, 2022 reply Follow Share 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. 0 votes 0 votes Shoto commented Jan 21, 2022 i edited by Shoto Jan 21, 2022 reply Follow Share @atulcse 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 @raja11sep @ankit3009For a given string and some ambiguous grammar producing it, is #LMD = #RMD always true? 2 votes 2 votes atulcse commented Jan 21, 2022 reply Follow Share 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 votes 0 votes Shoto commented Jan 21, 2022 reply Follow Share @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 votes 3 votes ankit3009 commented Jan 21, 2022 reply Follow Share 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 votes 2 votes shivmodi94 commented Dec 28, 2022 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.