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

@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