256 views

Consider the grammar ‘G’ given below:
S → aSa | bSb | a | b | ϵ
Which of the following option is incorrect?

1.   G is ambiguous
2.   G is unambiguous
3.   G generates palindrome strings
4.   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??

| 256 views

+1 vote

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.

by Boss (28.7k points)
selected
+1
so,it can be said that even if a grammar is left recursive and not left factored,still it can be unambigous...??
option 1 is wrong. because ther exists only one derivation tree for any given string
by Junior (629 points)