Let E = {a^i b^j | i != j and 2i != j}. Show that E is a context-free language.
I'm having trouble where to begin making the grammar. Could anyone give me a push in the right direction?
Thank you.
Note that i != j and 2i != j is equivalent to 2i < j or j < 2i < 2j or i > j. The trickiest part is to generate {a^i b^j | j < 2i < 2j}. Let R(i, j) be j < 2i < 2j. I have a hypothesis, which I have not fully checked, that R can be defined inductively as follows.
(1) For all k > 1, (k, 2k - 1) is in R.
(2) For all i, j, if (i, j) is in R, then (i + 1, j + 1) is in R.
In turn, the relation S(i, j) <=> i > 1 and j = 2i -1 can be inductively generated like this.
(1) (2, 3) is in S.
(2) For all i, j, if (i, j) is in S, then (i + 1, j + 2) is in S.