Use the Pumping Lemma for CFLs to prove that L 0n1n0n1nn0 is

Use the Pumping Lemma for CFLs to prove that L= {0ⁿ1ⁿ0ⁿ1ⁿ|n0} is not context free. Hint: choose s=0^p1^p0^p1^p, where p is the pumping length for L. Consider these cases: (i) either v or y contain more than one type of symbol and (ii) both v and y contain (at most) one type of symbol.

Solution

The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be \"pumped\" without producing strings outside L.

Its not easy to keep 0\'s and 1\'s matched or to keep 1\'s and 2\'s ,matched or to keep the 0\'s and 2\'s matched there is no way to keep all three symbols matched simultaneously.
By the pumping lemma, there exists an integer p which is the pumping length of language L
Consider the string s = 0p1p0p1p in L
The pumping lemma tells us that s can be written in the form s = uvwxy, where u, v, w, x, and y are substrings, such that |vwx| p, |vx| 1, and uviwxiy is in L for every integer i 0. By the choice of s and the fact that |vwx| p, it is easily seen that the substring vwx can contain no more than two distinct symbols. That is, we have one of five possibilities for vwx:

    vwx = aj for some j p.
    vwx = ajbk for some j and k with j+k p.
    vwx = bj for some j p.
    vwx = bjck for some j and k with j+k p.
    vwx = cj for some j p.

it is easily verified that uviwxiy does not contain equal numbers of each letter for any i 1. Thus, uv2wx2y does not have the form 0i1i1i0i. This contradicts the definition of L. Therefore, our initial assumption that L is context free must be false