Using Pumping Lemma, prove that the following language is not regular

L ={ ww|w ε {0,10*}}

If L is regular, then by P.L. for all x ∈L with |x| ≥ n such that ∃u, v, w such that

(1) x= uvw

(2) |uv| ≤ n

(3) |v| ≥ 1

(4) $∀ i ∈ N :uv^iw∈ L.$

Let us consider $x = 0^n0^n∈L$

Here, |x| ≥ n.

Let $u = \epsilon, v = 00, and w = 0^{2n-2}$

Then $∀i ,uv^iwis of the form 0^{2k}= 0^k0^k.$

We check if $0^n0^n can be written as 0^n0^n= uvwsuch that |uv| ≤ n |v| ≥ 1 and that for all i: uv^iw∈ L$

Now let$ x = (01)^n(01)^n$

We check if this string can be pumped

So, if we take

$u =\epsilon, v = 0101, w = (01)^{2n-2}$ it can be pumped

Now, we consider $x = 0^n10^n1$

such that $∀u, v, w such that 0^n10^n1 = uvw and |uv| ≤ n and |v| ≥ 1$must have uv contained in the first group of $0^n$

Thus, we consider

$uv^0w = 0^{n−|v|}10^n1.$

Since |v|is at least 1, this is clearly not of the form ww.

Hence, as L is not of the form ww, our assumption is false.

Therefore, L is not regular.