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

Problem Detail: 

$L = \{0^i1^j0^i1^j|i,j \geq 0\}$

I've tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated.

Asked By : user678392

Answered By : Patrick87

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14559