Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as…

2007

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:

For the string aabbab, how many derivation trees are there?

Answer: B. 2 — S → aB → aaBB → aabB → aabbS → aabbaB → aabbab S → aB → aaBB (till now, only 1 choice possible) → aabSB (last time we took B → b, now taking B → bS) → aabbAB…

  1. A.

    1

  2. B.

    2

  3. C.

    3

  4. D.

    4

Attempted by 16 students.

Show answer & explanation

Correct answer: B

S → aB
 → aaBB
 → aabB
 → aabbS
 → aabbaB
 → aabbab

S → aB
 → aaBB   (till now, only 1 choice possible)
 → aabSB  (last time we took B → b, now taking B → bS)
 → aabbAB
 → aabbaB
 → aabbab

So, totally 2 possible derivation trees.

Correct Answer: B

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…