Assume that L is regular. Let p be the pumping length guaranteed by the Pumping Lemma.

Take w =0^{p}10^{p}1 . Clearly, w ∈ L, and |w| ≥ p. We need to show that for any partition w = xyz, with |xy| ≤ p, and y≠∈, there exists i ≥ 0, such that xy^{i}z ∉ L.

Let k = |y|. Note that 0 < k ≤ p. Then, xy^{0}z = 0^{p−k}10^{p}1 ∉ L , because if it were in L, then for some string u, we must have 0^{p−k}10^{p}1 = uu, which implies that u ends with 1, and so p − k = p, which is impossible because k ≠ 0.

This explanation revolves around proving that the language L={ww∣w∈{0,1}∗}L = { ww mid w in {0, 1}^* }L={ww∣w∈{0,1}∗} is not regular by using the **Pumping Lemma** for regular languages. Let’s break it down step by step:

### The Pumping Lemma

The **Pumping Lemma** states that for any regular language LLL, there exists a pumping length ppp such that any string www in LLL with a length of at least ppp can be divided into three parts w=xyzw = xyzw=xyz with the following conditions:

**Length Condition**: ∣xy∣≤p|xy| leq p∣xy∣≤p**Non-Empty Condition**: ∣y∣>0|y| > 0∣y∣>0**Pumping Condition**: For all i≥0i geq 0i≥0, the string xyizxy^izxyiz must also be in LLL.

### Assumption and Choice of String

**Assumption**: We start by assuming LLL is regular.**Pumping Length**: Let ppp be the pumping length guaranteed by the Pumping Lemma.**String Selection**: We choose the string w=0p10p1w = 0^p 1 0^p 1w=0p10p1. This string belongs to LLL because it can be expressed as wwwwww where w=0p1w = 0^p 1w=0p1 (it repeats www twice).

### Applying the Pumping Lemma

Now, according to the Pumping Lemma, since ∣w∣≥p|w| geq p∣w∣≥p, we can split www into three parts w=xyzw = xyzw=xyz where:

- ∣xy∣≤p|xy| leq p∣xy∣≤p (meaning that xyxyxy consists of only the first ppp characters of www).
- y≠ϵy neq epsilony=ϵ (meaning yyy is not the empty string).

### Analysis of the Split

Since ∣xy∣≤p|xy| leq p∣xy∣≤p and www begins with 0p0^p0p:

- The part yyy can only contain 000s. Let’s denote the length of yyy as k=∣y∣k = |y|k=∣y∣. Thus, 0<k≤p0 < k leq p0<k≤p.

### Pumping Down

**Pumping Down**: We consider i=0i = 0i=0, which means we examine the string xy0z=xzxy^0z = xzxy0z=xz.**Resulting String**: The resulting string will be xy0z=0p−k10p1xy^0z = 0^{p-k} 1 0^p 1xy0z=0p−k10p1.**Checking Membership in LLL**: We must show that xy0z∉Lxy^0z notin Lxy0z∈/L.

### Why xy0z∉Lxy^0z notin Lxy0z∈/L

To show that 0p−k10p1∉L0^{p-k} 1 0^p 1 notin L0p−k10p1∈/L:

- If 0p−k10p10^{p-k} 1 0^p 10p−k10p1 were to belong to LLL, it would have to be expressible as uuuuuu for some string uuu.
- The string uuu must end with a 111 because the second half of uuu (i.e., after the first 111) starts with 0p0^p0p (i.e., 0p10^p 10p1 is in the first half).
- Therefore, if uuu ends with 111, the condition requires that the length of the first part before the second half also equals the length of the second part.

Thus:

- We get ∣u∣=p−k+1|u| = p-k+1∣u∣=p−k+1 (from 0p−k10^{p-k}10p−k1) which must equal ∣0p1∣=p+1|0^p1| = p+1∣0p1∣=p+1.
- Since kkk is positive, p−kp – kp−k cannot equal ppp, leading to a contradiction.

Since we derived a contradiction from our assumption that LLL is regular, we conclude that the assumption is false, and thus **LLL is not a regular language**. This example effectively demonstrates how the Pumping Lemma can be used to prove non-regularity.