1 votes 1 votes How is this grammar Ambiguous?? S-> SS+ / SS* / a Can anyone give me an example of a string with parse trees ,I am unable to find such string. atul_21 asked Nov 28, 2017 atul_21 1.3k views answer comment Share Follow See all 17 Comments See all 17 17 Comments reply just_bhavana commented Nov 28, 2017 reply Follow Share because it is not an ambiguous grammar. It is left recursive but not ambiguous. 0 votes 0 votes joshi_nitish commented Nov 29, 2017 reply Follow Share how you decided that it is not an ambigous grammer ? 0 votes 0 votes just_bhavana commented Nov 29, 2017 reply Follow Share I know it is undecidable but there is no string for which multiple parse trees are possible 0 votes 0 votes joshi_nitish commented Nov 29, 2017 reply Follow Share how can you say that "there is no string for which multiple parse trees are possible" there are infinite strings generated by above grammer, if you will check, you will keep on checking till eternity. if the qsn was prove that ->it is ambigous grammer, then you can arrive at answer after some time.. according to me these types of qsns should not be asked in exam in which, qsn is -> "whether grammer is ambigous or not ?" and answer is 'no' 0 votes 0 votes just_bhavana commented Nov 29, 2017 reply Follow Share so you're saying there might be a rare possibility that a string generated by the above grammar will give multiple parse trees? but can we not infer this from the pattern of strings generated ? 0 votes 0 votes Shivam Chauhan commented Nov 29, 2017 reply Follow Share I agree with @joshi_nitish 0 votes 0 votes joshi_nitish commented Nov 29, 2017 reply Follow Share @just_bhavana if the pattern is highly conclusive, then yes you can infer from it that grammer is unambigous. for ex: S->aS /ε, this is definately unambigous grammer. but sometimes, it appears that we have found some pattern and we conclude that grammer is unambigous, which is actually ambigous... 1 votes 1 votes just_bhavana commented Nov 29, 2017 reply Follow Share yes I completely agree, even finding the string which generates multiple parse trees is difficult sometimes. Hence it is undecidable if a grammar is ambiguous 1 votes 1 votes atul_21 commented Nov 29, 2017 reply Follow Share Answer given was it is ambiguous.. . But how? 0 votes 0 votes Hemant Parihar commented Nov 29, 2017 reply Follow Share @joshi_nitish, Is the string "aa" can't parse like this? S --> SS+ --> aS+ --> aa. S --> SS* --> aS* --> aa. 0 votes 0 votes joshi_nitish commented Nov 29, 2017 reply Follow Share @Hemant Parihar former one is derivation for aa+ and later one for aa*, and both are different strings. 0 votes 0 votes joshi_nitish commented Nov 29, 2017 reply Follow Share moreover string 'aa' is not generated by above grammer. 0 votes 0 votes Hemant Parihar commented Nov 29, 2017 reply Follow Share The string is a finite sequence of character. aa+ and aa* is not a string. 0 votes 0 votes joshi_nitish commented Nov 29, 2017 reply Follow Share does grammer ever contain kleen closer(*) and positive closer(+) symbol ? 0 votes 0 votes Hemant Parihar commented Nov 29, 2017 reply Follow Share No, it is not present. 0 votes 0 votes joshi_nitish commented Nov 29, 2017 reply Follow Share here in TOC string not only means set of characters.. if input symbol = $\sum$(a,b,*,+) then language L $\subseteq$ $\sum$(a,b,*,+) have strings as aa+, a, +, *, aa+b*a++.....etc 0 votes 0 votes Hemant Parihar commented Nov 29, 2017 reply Follow Share Oh.. Understood. Thank you :) 0 votes 0 votes Please log in or register to add a comment.