Home » Compiler Design » Compiler design miscellaneous » Question

Compiler design miscellaneous

  1. Which one of the following grammars generates the language L = {ai bj} i ≠ j]?
    1. S → AC | CB
      C → aC b |a|b
      A → aA | ∈
      B → bB | ∈
    2. S → aS | Sb |a| b
    3. S →AC | CB
      C → aC b | ∈
      A → aA | ∈
      B → Bb | ∈
    4. S → AC | CB
      C → aC b | ∈
      A → aA |a
      B → bB |b
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.



Your comments will be displayed only after manual approval.