⟸ Go Back ⟸
Exercise 4 (Homework 3).
(pumping lemma, hard exercise)

Palindromes and partial palindromes

  1. Show that the language \{w\in \{a,b\}^* \mid w=w^R\} is not regular.

  2. Show that the language \{ww^R\mid w\in \{a,b\}^*\} is not regular.

  3. Show that the language \{ww\mid w\in \{a,b\}^*\} is not regular.

  4. (hard) Show that the language \{ww^Rx\mid w,x\in \{a,b\}^+\} is not regular.

    Caution

    For this last point, the pumping lemma cannot be used to show non-regularity. Why?

    Suppose, towards a contradiction, that the language is regular and there is a DFA with N states recognizing it. Test the behaviour of the automata against all the words w_i=aba^2b^2\cdots a^ib^i, for i=1,2,\dots, N+1.