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

in Compiler Design 743 views

3 Answers

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.

selected by
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
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.

Related questions

2 votes
2 answers
Which of following is correct? 1). Drawback with static allocation is that it does not support recursion. 2). Drawback with stack allocation is that, when function completes its execution it will be popped out from stack.. 3). Both are correct 4).None of above
asked Oct 20, 2015 in Compiler Design Pooja Palod 370 views
1 vote
1 answer
1.Class of grammar that will parse using LR method is proper subset of class of grammar that will parse with predictive parser . 2. LR Parser can be constructed to recognize virtually all programming language constructs for which CFG can be written . Please give valid justification for each point even if it is false
asked Apr 30, 2018 in Compiler Design radha gogia 598 views
0 votes
0 answers
Which of the following statement/s is/are false for the following language: L = {am bn cq | m = n or n = q, m > 0, n > 0, q > 0} S1: The language can be parsed by any LR(K) parsers for any value of K. S2: The language cannot be recognized by deterministic PDA. Only S2 Only S1 Both S1 and S2 Neither S1 nor S2
asked Dec 10, 2016 in Compiler Design Akriti sood 809 views
2 votes
1 answer
Which of the following symbol table implementation is based on the property of locality of reference? Self-organizing list Hash tree Search tree Array
asked Dec 8, 2016 in Compiler Design Akriti sood 5.6k views