2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.