MHB Pumping Lemma proof for L=0^p 1^p 0^p 1^p-: Review my proof please-:

[shivajikobardan]

Please review my proof. Is this correct or not?

 

[Evgeny.Makarov]

Why do you consider case 1) where $v=0^p$, $x=1^p$ and $y=\varepsilon$? It is prohibited by condition (2) of the lemma.

In case 3) you write: "$L$ contains pattern not in form $0^p1^p0^p1^p$". This is true: $L$ contains words that do not have this form and do not even have the form $0^n1^n0^n1^n$ for any $n$. What conclusion do you draw from this? Then you write: "So $\notin L$. What exactly does not belong to $L$? It's a bad style to write such ambiguous claims in a proof. Finally, case 3) assumes that $y=\varepsilon$. What if this is not so?

The description of case 5) is not clear (does $y$ have to be empty? does $x$ has to end on the boundary between zeros and ones?), but it seems that it is again prohibited by condition 2 of the lemma.

A proof should contain more words. For example, this proof should start like this: "Let $p$ be the number whose existence is stated in the lemma. Let $w=0^p1^p0^p1^p$. Consider the following five exhaustive cases".

Please type you proof in the body of the forum post. Pictures can easily be described, for example: "$vxy$ spans the first boundary between 0s and 1s" (the diagram at the bottom of page 1). The bottom of page 1 is far too dark for comfortable reading.