# Verification of “Prove/Disprove that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is context free.”

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.