Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free?

I cannot go on with this exercise:

Determine whether $L = \{a^nb^m \mid n > 2^m \}$ is context-free.

Let's suppose that $L$ is context-free. According to the pumping lemma, there exists $N > 0$ such that every $z \in L$ of size at least $N$ has a decomposition $z = uvwxy$ such that

1. $|vwx| \leq N$.

2. $|vx| \geq 1$.

3. For all $i \geq 0$, $z_i = uv^iwx^iy$ is in $L$.

Let's use $z= a^{2^N+1}b^N$.

Then $|z| = 2{^N+1} +N > N$ and $v= a^h$ and $x= b^k$ with $1 \leq h+k \leq N$.

So $z_i = a^{2^N+1}a^{h(i-1)} b^{N-k}b^{k(i-1)}$.

So if there exists $i > 0$ such that $2^N+1+h(i-1) \leq 2^{N+(i-1)k}$, then $z_i \notin L$.

How can I go on to show that $L$ is not context-free?

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Apr 10 '17 at 17:03
• Possible duplicate of How to prove that a language is not context-free? (Or How to prove that a language is context-free?) – David Richerby Apr 10 '17 at 19:24
• Well: if vwx is made only of "a" symbols, it's easy to proove that is always possible to make a string which does not belong to L (i = 0). If made of only "b" symbols, is possible to create a string which does not belong to L by increasing i. But, if vwx is made of both "a" and "b", I cannot imagine a possible solution which allows me to finally proove that L is not CF. – d.gigante13 Apr 10 '17 at 21:00
• I would find an i which invalidates the PL: to find it, I should use logarithm with 2 base but, if I do this, I have the i in the topic of the logarithm (first member) and so I cannot find a valid solution to the inequality since I have 2 separate i. How can I go on? Just this i need to know. – d.gigante13 Apr 11 '17 at 6:50

According to Parikh's theorem, if your language were context-free, then the set S = $\{(n,m) : n > 2^m\}$ would be semi-linear. Every linear subset of $S$ has a constant second coordinate, as we show below. Therefore you need an infinite number of linear sets to cover $S$, showing that it is not semi-linear.
It remains to show that every linear subset of $S$ has constant second coordinate. Indeed, consider any linear subset of $S$. By definition, such a subset is of the form $u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_r$. By assumption there exists some $i > 0$ such that $u_i = (a,b)$, where $b \neq 0$. Let $u_0 = (n',m')$. It is not hard to check that for some $t$, $n' + at \leq 2^{m' + tb}$, since the left-hand side grows linearly, whereas the right-hand side grows exponentially. This contradicts the fact that the subset is a subset of $S$.