COM1350 COM1350 Palindrome Pumping Lemma Sheet

Name:

Use the Pumping Lemma to prove that the set L of even length palindromes,

L = { w {a, b}* | w = ssR where s {a, b}* }

is NOT regular.

Proof:

Assume L is _______________________ and let p be ______________________________.

Let w =__________________ .

Then, by the pumping lemma, w = xyz where:

  1.  

  2.  

  3.  

Then, by _____________________________ y must be of the form y = ________________.

But then wí = xy_______z =___________________ is NOT _____________.
(fill in the superscript for y)

This _____________________________.

Hence L is ___________________________.

Q.E.D.

Last Updated: July 18 2001 9:51 p.m. by

Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: automata@harrietfell.com
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/COM1350/HW/palindromeProof.html