I attempt to show that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is not context free by applying the Pumping lemma for context-free languages.

This is achieved by a proof by contradiction by first assuming that $L$ is context free, in which case arbitrarily long strings in $L$ should be able to be "pumped" and still produce strings inside $L$. By "pumping" strings in $L$ to produce other strings which are not contained in $L$, then it cannot be true that the language $L$ is context free.

Progress so far:

The pumping lemma states that every string $s$ in $L$ can be written in the form

$ s = uvwxy$

with substrings $u, v, w, x, y$

such that

  1. $|vx| \geq 1$
  2. $|vwx| \leq p$
  3. $uv^nwx^ny \in L$ for all $n \geq 0$

so a suitable decomposition into the substrings $u, v, w, x, y$ must be found.

My informal approach is to consider on a case by case basis that each decomposition fails.

case 1:

If only the letter b is pumped, then there will be more than two b's the final string, which cannot be in L. For example:

$u = a^k, v = b, w = a^{2k}, x = b, y = a^{3k}$

by condition 3, $s = uv^nwx^ny \notin L$ for $n = 2$

case 2:

If only the letter a is pumped, then the distribution of the letter a in the pumped string will no longer be valid. For example:

$u = \varnothing, v = a^k, w = ba^{2k}b, x = a^{3k}, y = \varnothing$

case 3:

If both the letters a and b are pumped, then the order of letters will be invalid in the pumped string.

For example:

$u = \varnothing, v = a^kb, w = a^k, x = a^kb, y = a^{3k}$

case 4:

The case that neither the letter a nor the letter b is pumped fails because of the first condition.

In this solution I have neglected to consider both defining a pumping length $p$ ($p$ is still conceptually difficult for me and I don't know how to correctly define it) as well as the second condition of the pumping lemma.

I would be greatly appreciative for any assistance in this, as well as verifying/formalizing the above proposed solution.


Your Answer

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

Browse other questions tagged or ask your own question.