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, 2017 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?) Apr 10, 2017 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. Apr 10, 2017 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. Apr 11, 2017 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$.

• Sorry but I have not studied this Theorem and I don't know if the teacher would accept this type of solution. Is it possible to solve the problem using a mathematical method like the one I was using? Apr 11, 2017 at 12:30
• I don't care much what your teacher would or would not accept. After all, this is not a homework answering service. Doubtless the question can also be solved using the pumping lemma, but knowledge of other methods is more interesting from a broad perspective. Apr 11, 2017 at 23:38
• Ok. Thank you anyway. You are right but I would also see the PL solution. Apr 12, 2017 at 5:48