retagged by
1,700 views
3 votes
3 votes

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

retagged by

3 Answers

Best answer
2 votes
2 votes

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.

selected by
0 votes
0 votes
Option 3 is correct because the given grammar can generate both set of palindromes I.e even palindromes and odd palindromes too.
And there is no such rule for ambiguity of grammar like left factoring.
Answer:

Related questions

1 votes
1 votes
1 answer
1
eyeamgj asked Nov 12, 2018
293 views
S->ABA->aB->bthis grammar is ambiguous or not.Q2; is it true that the number of left most derivation tree is always equal to number of right most derivation tree.?
2 votes
2 votes
3 answers
2
Rahul Ranjan 1 asked May 28, 2018
1,393 views
If a grammar( $CFG$ ) has more than one Right most derivation, Can it be called ambiguous ?Or we say a grammar is ambiguous only when it has more than one left most deriv...
0 votes
0 votes
1 answer
3
Nikhil Patil asked Feb 7, 2018
335 views
$G: S\rightarrow SbS\mid a$Grammars are ambiguous True/False.