# Proving the given language isn't context free using Pumping Lemma

i want to prove that the following Language isn't CF

$L=\{a^kba^kba^k|k\in \mathbb{N}\}$

Let $z=a^nba^nba^n$ be a String from $L$

$n$ is the pumping length and $|z|=3n+2 > n$

and $z=uvwxy$ with $|vx|\geqslant 1$, $|vwx|\leqslant n$

but i'm not sure how to determine the correct substrings, how should i consider them ? I tried the ones below are thy correct ?

Case 1 : $u=a^n,\ uwx=ba^n,\ y=ba^n$

Case 2 : $u=a^{n-l},\ uwx=a^lb,\ y=a^nba^n$

Case 3 : $u=a^nb,\ uwx=a^nb,\ y=a^n$

Case 4 : $u=a^nba^{n-l},\ uwx=a^{l-k},\ y=a^kba^n$

Case 5 : $u=a^nb,\ uwx=a^n,\ y=ba^n$

• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Jul 9 '17 at 16:23

The pumping segments $v$ and $x$ can be anywhere in the string assuming they are at most $n$ apart, i.e., $|vwx|\le n$. Like you I get five possibilities, but I think you wrote some special cases rather than the general picture.

Inside one of the $a$-segments, for instance :

• the first $u=a^i$, $vwx=a^j$, $y=a^{n-i-j}ba^nba^n$ where $i+j\le n$ and $j\ge 1$. Or
• the second $u=a^nba^i$, $vwx=a^j$, $y=a^{n-i-j}ba^n$ where $i+j\le n$ and $j\ge 1$. Or
• the third $\dots$ .

Or overlapping with one of the $b$'s. Of course because of the lengths we cannot overlap with both $b$'s.

• First: $u=a^{n-i}$, $vwx=a^iba^j$, $y=a^{n-j}ba^n$ where $0\le i,j\le n$, $i+j< n$ .
• Second $\dots$ .

However this does not solve the pumping problem. Note we repeat the strings $v,x$ when pumping. In these last cases we do not know how $v,x$ look. Do they contain the $b$? More cases.

A shortcut to the proof would be to make the following observation.

1. The pumping segments cannot contain $b$.

That leaves five cases for the position of $v$, $x$ in the three $a$-segments. Either deal with them or argue

1. Now that $v$, $x$ can only contain $a$'s we can pump either one or two of the three $a$-segments in $z$. That means after pumping they cannot all contain the same number of $a$'s
• thank you for the help, this helped me, i wrote these special cases because my professor told us that we must consider all possible cases of sub strings and then argue for each one by choosing a random pumping length mostly from $i\in\{0,1,2\}$ and pumping each case then see if it's still from the given Language – proless8 Jul 10 '17 at 16:33