The Gateway to Computer Science Excellence
+3 votes
248 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??

in Compiler Design by Boss (12.2k points) | 248 views

3 Answers

+1 vote
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.

by Boss (28.6k points)
selected by
+1
so,it can be said that even if a grammar is left recursive and not left factored,still it can be unambigous...??
0 votes
option 1 is wrong. because ther exists only one derivation tree for any given string
by Junior (619 points)
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.
by (23 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,503 answers
195,553 comments
101,037 users