[Solved]: Prove L to not context free using pumping lemma on language L

Take a look at the following proof; if this is “nasty”, you might just be too picky. 🙂 Consider the string $0^p1^p0^p1^p in L$. The string consists of four distinct parts with three boundaries separating the parts: $0^p1^p0^p1^p = (0^p)(1^p)(0^p)(1^p)$. By the pumping lemma for context-free languages, this string can be written as $uvxyz$ such that $vxy leq p$ and $uv^kxy^kz in L$. We must now determine what values the substring $vxy$ may assume. There are seven interesting cases:

• The substring $vxy$ consists entirely of one of the four parts of the string (four cases); or
• The substring $vxy$ consists of symbols from two adjacent parts and encompasses exactly one of the three boundaries (three cases).

Consider a representative of the first set of four cases; e.g., assume $vxy$ consists entirely of $0$s from the first part of the string. Pumping $vxy$ will change the number of $0$s in the first part of the string without affecting the number of $0$s in the third part, so we will not get a string in $L$. Similar reasoning applies to the other three cases. Consider a representative of the second set of three cases; e.g., assume $vxy$ consists entirely of $0$s and $1$s from the first and second parts of the string. Pumping $vxy$ will change the number of $0$s from the first part of the string, and the number of $1$s from the second part, without affecting the number of symbols in the third and fourth parts of the string. Therefore, any pumped string cannot possibly be in $L$. Similarly reasoning applies to the other two cases. Since, in each of the seven cases, pumping the substring fails to produce a string in $L$, we have a contradiction, namely, we assumed that the language is context free, but have found that the pumping lemma for context-free languages does not hold. We conclude that our assumption was incorrect, i.e., that $L$ must not be context-free.