0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 10 '17 at 17:03
  • 2
    $\begingroup$ Possible duplicate of How to prove that a language is not context-free? (Or How to prove that a language is context-free?) $\endgroup$ – David Richerby Apr 10 '17 at 19:24
  • $\begingroup$ 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. $\endgroup$ – d.gigante13 Apr 10 '17 at 21:00
  • $\begingroup$ 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. $\endgroup$ – d.gigante13 Apr 11 '17 at 6:50
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – d.gigante13 Apr 11 '17 at 12:30
  • 3
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 11 '17 at 23:38
  • $\begingroup$ Ok. Thank you anyway. You are right but I would also see the PL solution. $\endgroup$ – d.gigante13 Apr 12 '17 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.