2.24 Sipser: Let E = { aibj i ≠ j and 2i ≠ j } Show that D is context-free language.

2.24 Let E = { aⁱb^j  | i ≠ j and 2i ≠ j } Show that D is context-free language.

solution:

Split it as unions of  3 languages.

{ aⁱb^j | i > j } ∪ { aⁱb^j | i < j and 2i > j } ∪ { aⁱb^j | 2i < j }

G¹ = { aⁱb^j | i > j }

G² = { aⁱb^j | i < j and 2i > j }

G³ = { aⁱb^j | 2i < j }

G¹ and G³ are quite easy to figure out.
for G¹

S →   aSb | aS¹
S¹ → aS¹ |ε

for G³

S → aSbb | S¹b
S¹ → S¹b | ε

Now tricky part is G2.

S → aSb | aS¹b
S¹ → aS¹bb | aS²bb
S² → ε

Very clearly, S will generate aⁿa^mb^2mbⁿ that is equivalent to a^n+mb^n+2m where m,n must be greater than 0.

Feel free to comment and correct me if I am wrong. :)