0
$\begingroup$

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.

$\endgroup$

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.