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

2021

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 :

S → bA S → aB
A → a B → b
A → aS B → bS
S → bAA B → aBB

Which of the following strings is generated by the grammar?

  1. A.

    aaaabb

  2. B.

    aabbbb

  3. C.

    aabbab

  4. D.

    Abbba

  5. E.

    Question not attempted

Attempted by 32 students.

Show answer & explanation

Correct answer: C

Try derivation using rules:

S → aB
B → bS
S → aB
B → b
A → a

One valid derivation:

S ⇒ aB
⇒ abS
⇒ abaB
⇒ abab
⇒ aabbab (using recursive expansions with A → a, B → bS / b)

Hence, aabbab can be generated.

Explore the full course: Bpsc