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.

Printable View

- April 18th 2011, 07:07 PMxwanderingpoetxContext free language question.
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. - April 19th 2011, 01:02 AMemakarov
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.