Proving a language is not context-free (pumping lemma)

Question

below is my attempt at applying the pumping lemma to a language to prove that it is not context-free. I am new to using the pumping lemma, especially for context-free languages. My question is, is this the right way to apply the pumping lemma to prove a language is not context-free? Can any modifications or corrections be made?

---

Let L = $ \{ a^m b^n|m,n>0 $ and $m \geq 2n \} $

Assume L is context-free. Therefore, pumping lemma applies. Let P be the Pumping Length.

There exists a string long enough $\geq P$. We'll use $w = a^{2P}b^p = uvxyz$.

$|w| = 3P$

$|vxy| \leq P$

$|vy| \neq 0$

$vxy$ can contain :

• only a's
• only b's
• Some a's and b's

$vxy$ cannot contain:

• more than half of all a's
• more than all b's

$uv^ixy^iz \in L $ because P.L.

Let $i = 2: uv^2xy^2z \in L$

$|uv^2xy^2z| > 3P$

$a^{2P}b^{(P + j)} \notin L $ if j is $ > 0$

The # of b's becomes too great to satisfy the language.

Therefore, $uv^2xy^2z \notin L$, and this is a proof by contradiction.

Answer 1

You started correctly, but you went astray after describing what $vxy$ can be. You really need to consider separately how pumping affects $w$ in each case.

• If $vxy$ contains only $a$s, then $uv^kxy^kz$ will have too few $a$s if $k=0$ and too many if $k>1$, so in fact $k=1$ is the only value of $k$ for which $uv^kxy^kz\in L$.

• If $vxy$ contains only $b$s, then $uv^kxy^kz$ will have too few $b$s if $k=0$ and too many if $k>1$, so in fact $k=1$ is again the only value of $k$ for which $uv^kxy^kz\in L$.

The interesting case is when $vxy$ contains both $a$s and $b$s, and there you run into trouble: it’s possible that $v=aa$, $x$ is empty, and $y=b$. In that case

$$uv^kxy^kz=a^{2p-2+2k}b^{p-1+k}=a^{2(p-1+k)}b^{p-1+k}\in L$$

for every $k\ge 0$.

In fact $L$ is context-free: it’s generated by the context-free grammar with initial symbol $S$ and the following productions:

$$\begin{align*} &S\to aaSb\mid A\\ &A\to aA\mid\lambda \end{align*}$$

(Here $\lambda$ is the empty string; another notation for it is $\epsilon$.)