Consider the following context free grammar S → SS + | SS*| a Which of the…
Consider the following context free grammar
S → SS + | SS*| a
Which of the following statement/s is/are correct with respect to the grammar?
S1: The grammar has leftmost derivation for the string aa + a*
S2: The grammar has rightmost derivation for the string aa + a *
S3: Since the grammar has left most derivation as well as right most derivation so it is ambiguous grammar.
Answer: C. Only S1 and S2 are true. — The leftmost derivation for string aa + a* is: S = lm ⇒SS* ⇒SS + S* ⇒aS + S* ⇒ aa + S* ⇒ aa + a* So the statement S1 is true. The right most derivation for…
- A.
Only S3 is true.
- B.
All S1, S2 and S3 are true.
- C.
Only S1 and S2 are true.
- D.
Only S1 is true.
Attempted by 124 students.
Show answer & explanation
Correct answer: C
The leftmost derivation for string aa + a* is:
S = lm ⇒SS* ⇒SS + S* ⇒aS + S* ⇒ aa + S* ⇒ aa + a*
So the statement S1 is true.
The right most derivation for string aa + a* is:
S = r m ⇒ SS* ⇒Sa* ⇒ SS + a* ⇒Sa + a* ⇒ aa + a*
So the statement S2 is true.
Statement S3 is not true i.e., since the grammar has left most derivation as well as right most derivation but it is not capable of generating different parse trees for any
string generated by the grammar and hence it is not ambiguous grammar.
Please note a grammar is ambiguous if it has two different parse tree for any string by using either LMD only or by using either RMD only.