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