Pumping Lemma Disproving Regular Language Example

Example

With $\Sigma =\{0,1\}$ With $L=\{x\in {\Sigma }^{\ast }:x^R=x\}$ Prove $L$ is not regular.

• Suppose For sake of Contradiction, that $L$ is Regular Language
• Let $n$ be as in the Pumping Lemma
• Let $x=0^{n}10^n\in L$
• Then, $|x|=2n+1\ge n$
• Choose $u=0^j$ for some $j\in 0<k\le n$
• By 4, $u{v}^{2}w=uvvw=0^{n+j}10^n\notin L$ as its not reversible
• Thus, we have a contradiction.