-
Which one of the following grammars generates the language L = {ai bj} i ≠ j]?
-
- S → AC | CB
C → aC b |a|b
A → aA | ∈
B → bB | ∈
- S → aS | Sb |a| b
- S →AC | CB
C → aC b | ∈
A → aA | ∈
B → Bb | ∈ - S → AC | CB
C → aC b | ∈
A → aA |a
B → bB |b
- S → AC | CB
Correct Option: D
In the language language L = {ai bj | i ≠ j} The expression i ≠ j indicates that language L is a language in which number of a ≠ number of b. Here, we need to search for a language in which number of a ≠ number of b.
Considering the options:
Options (a)
S → AC | CB
C → aCb | a| b
A → aA | ∈
B → Bb | ∈
(a), S → (C) B → a(b) → aBb → ab
Here, the number of a = number of b, hence, it is not the required grammar.
Option (b)
S → as | Sb | a | b
S → as → abB
Here, number of a = number of b, hence it is not the required grammar.
Option (c)
S → AC | CB
C → aC b| ∈
A → aA | ∈
B → Bb | ∈
S(C)B → acbB → ab
Here, number of a = number of b, hence it is not the required grammar.
Option (d)
S → AC | CB
C → aC b| ∈
A → aA | a
B → Bb | b
Consider the production
S → AC | CB
Applying, C → ∈
We get S → A|B
Now, applying A or B, S generates a^n.b^n. So, L = {ai bj | i ≠ j}
Now, consider the production, S → AC | CB. If the production C → acb is applied then, it generates a^n,b^n.
Now, applying either A or B it will give that number of a ≠ number of b.