GATE IT 2008 | Question: 79

Question

$A$ CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and a and b are terminals.

• $S → aS \mid A$
• $A → aAb \mid bAa \mid \epsilon$

For the string "$aabbaab$" how many steps are required to derive the string and how many parse trees are there?

• A. $6$ and $1$
• B. $6$ and $2$
• C. $7$ and $2$
• D. $4$ and $2$

Comments

Look at second production:- Equal a and b combinations

In given,we need 4 a and 3 b

From S,if we have two options but if we take second we cannot cant unequal a and b.

So we have to start with S->aS, now as we have taken one a.Now needed is 3 a and 3b in some order and there is only one way to get this from A.

It seems like we have to explore lot of options ,but there is always something in gate questions that helps to get quick answer:)

---

Quick tip: a grammar is ambiguous only when it has both left and right recursion in its productions. Since the given grammar contains only one type of recursion, it is unambiguous. Therefore, it allows only a single parse tree, so Option A is correct.

---

thanks this was useful

---

@nithin_9 

small addition:

Ambiguous grammar can be easily detected if it is both left and right recursive + it derives $pure\ terminal$ production also

$S \rightarrow SS \ |\ a$     is ambiguous  

if grammar is just left and right recursive then it need not be ambiguous

---

@panipuri

 

This is a major misconception. The only reliable test for ambiguity is whether some string generated by the grammar has more than one parse tree (or equivalently, more than one LMD/RMD).

---

@dhawalphalak35

okay give me a Grammar which is in the form i mentioned but is NON-AMBIGUOUS 

Answer 1

$S\underset{1}{ \rightarrow} aS$
$\quad \underset{2}{\rightarrow} aA$
$ \quad \underset{3}{\rightarrow} aaAb$
$\quad \underset{4}{ \rightarrow} aabAab$
$\quad \underset{5}{ \rightarrow} aabbAaab$
$\quad \underset{6}{ \rightarrow} aabbaab$

Thus $6$ steps are needed and only one way to derive the string so only one parse tree.

Correct Answer: $A$

Comments

if we look at the Non Terminal, A  it is very much clear that we can produce only even length strings out of it.

That means our given string which is $'aabbaab'$ (length =7) can not be derived by production $S \rightarrow A$ or solely with $A$.

Hence we are bound to start our derivation with production: $S \rightarrow aS$.

---

Grammar is unambiguous.So only one parse tree is present for a string.

---

LIKITH P

nice :)

Answer 2

As the https://gateoverflow.in/3393/gate-it-2008-question-79?show=3398#a3398 answer as he did top-down if also did bottom-up we will use same no.of reductions to make it to S