Which one of the following grammars generates the language L = {ai bj | i ≠ j}

2006

Which one of the following grammars generates the language L = {ai bj | i ≠ j}

  1. A.

    A

  2. B.

    B

  3. C.

    C

  4. D.

    D

Attempted by 9 students.

Show answer & explanation

Correct answer: D

The language L = {a^i b^j | i ≠ j} requires generating strings where the number of a's is not equal to the number of b's. Option D uses S → AC | CB, where A generates a^+ and C generates b^*, allowing for unequal counts. The productions A → aA | a ensure at least one 'a', and C → aCb | ε generate balanced strings, but the choice between AC (more a's) and CB (more b's) ensures i ≠ j. This structure correctly captures the language.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir