Prove that L = {ww | w ∈ {0, 1}∗} is not regular

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

Take w =0^p10^p1 . 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ⁱz ∉ L.

Let k = |y|. Note that 0 < k ≤ p. Then, xy⁰z = 0^p−k10^p1 ∉ L , because if it were in L, then for some string u, we must have 0^p−k10^p1 = 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.