Chapter 13.4, Problem 25E

Show that the set of palindromes over {0, 1} is not regular using the pumping lemma given in Exercise 22. [Hint: Consider strings of form 0^N10^N]

*22. One important technique used to prove that certain sets not regular is the pumping lemma. The pumping lemma states that if $M=\left(S,I,f,s_0,F\right)$ is a deterministic finite-state automaton and if x is a string in $L\left(M\right)$ , the language recognized by M, with $l\left(x\right)\ge \left|s\right|$ , then are strings u, v, and w in I* such that $x=uvw,l\left(uv\right)\le \left|s\right|$ and $l\left(v\right)\ge 1$ , and $u{v}^i\in L\left(m\right)$ for $i=0,1,\mathrm{2...}$ Prove the pumping lemma. [Hint: Use the same idea as was used in Example 5.]