Which of the following strings will correctly match the Grammar G represented…

2025

Which of the following strings will correctly match the Grammar G represented by production rules given?

image.png

  1. A.

    accbb

  2. B.

    aacbb

  3. C.

    abaed

  4. D.

    aaebb

Attempted by 23 students.

Show answer & explanation

Correct answer: B

The grammar defines two distinct languages based on the start symbol S -> A | B.

1. For A (A -> aAb | c): This generates strings with 'a's on the left, 'c' in the center, and an equal number of 'b's on the right. Pattern: a^n c b^n (where n >= 0). Example derivation for 'aacbb': S -> A -> aAb -> aaAbb -> aacbb.

2. For B (B -> bBd | e): This generates strings with 'b's on the left, 'e' in the center, and an equal number of 'd's on the right. Pattern: b^m e d^m (where m >= 0).

Any valid string must match one of these two patterns.

Explore the full course: Isro