Prove that L = {w | w = w^R,w ∈ {0, 1}*} is not regular (This is the language of binary palindromes)

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

Take w =0p10p. 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, xy 0z =  0p−k10p ∉L, because if it were in L, then 0p−k10p = ( 0p−k10p )R =  0p10p-k, and so p − k = p, which is impossible because k ≠ 0.

Leave a Reply