Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Consider the grammar $S\to SbS\mid a$.

Consider the following statements:

The string $abababa$ has

(A) two parse trees

(B) two left most derivations

(C) two right most derivations

Which of the following is correct?





Solution

Given grammar is:

$S\to SbS\mid a$

This grammar is ambiguous.

The string is:

$abababa$

It contains $4$ symbols $a$ and $3$ symbols $b$.

This is like combining four $a$'s using three $b$ operators.

Because the grammar does not define a fixed grouping rule, the string can be derived in more than one way.

For example, one possible grouping is:

$(((a)b(a))b(a))b(a)$

Another possible grouping is:

$(a)b((a)b((a)b(a)))$

So, the string has more than one parse tree.

For every different parse tree, there is a corresponding different left most derivation.

So, it has more than one left most derivation.

Similarly, for every different parse tree, there is a corresponding different right most derivation.

So, it has more than one right most derivation.

Therefore, all three statements are true in the sense of ambiguity.


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...