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}

- A.
A
- B.
B
- C.
C
- 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.