3 votes

Consider the grammar ‘G’ given below:

S → aSa | bSb | a | b | ϵ

Which of the following option is incorrect?

- G is ambiguous
- G is unambiguous
- G generates palindrome strings
- There exists only one left most derivation for a given string.

the grammar does not has left factoring,so is;nt this grammar ambigous??but i am getting only on eparse tree for any string.

but,if a grammar needs left factoring then grammar is ambigous..right??

2 votes

Best answer

This question can be answered only by looking at options, ofcourse answer has to be (A) or (B) because a grammar cannot be both ambiguous and unambiguous. And option (D) also says grammar is unambiguous. Thus (A) has to be answer.

And non-determinism is a problem when we don't know which production to take to get the required string. And Left-factoring is used to remove non-determinism(not ambiguity). So, it may be the case that a grammar is not ambiguous but needs left factoring.

Consider: $S \rightarrow aa | ab$ ($\color{green}{not\;ambiguous\;but\;needs\;left\;factoring}$)

And there is not doubt that $\color{navy}{S \rightarrow aSa\;|\;bSb\;|\;a\;|\;b\;|\; \epsilon}$ generates all even and all odd length palindromes, and for every string only one parse tree can be given. So, this grammar is unambiguous.