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 =0p10p1 . 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 xyiz ∉ L.

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

Leave a Reply