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:)

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

how  to be sure about  "only one such way" in exam?

how to declare that. with confidence. with negative marking?

---

without :P

Derivation in each step is shown. Actually a corresponding production is implied. At each step only 1 choice for production.

---

linz describes that more than one parse tree can be constructed if there exsists two or more leftmost or rightmost derivations. according to that there should be more tha one parse tree.

---

should we not count substituting $\epsilon$ as a separate step and then eliminating it, making it 7 steps(one extra with this)

or is $\epsilon$ counted as a terminal and we don't have to count?

---

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 :)