# Prove that a language is not regular

I want to prove that $L$ is not regular: $$L = \{ww^Rv \mid |w|\ge1 , |v|\ge 0\},$$ where the alphabet contains at least two symbols.

Can someone prove it?

I prefer to use "Pumping Lemma for Regular Languages" to prove it, but I think that's somehow impossible!

• What is the alphabet? – Brian M. Scott Nov 30 '15 at 15:56
• @BrianM.Scott result and proof should be same for any alphabet with > 1 symbol. – djechlin Nov 30 '15 at 16:00
• Nonetheless {0,1} is usually implied. – djechlin Nov 30 '15 at 16:00
• Yes you need >1 symbol (otherwise $L$ is regular). – BrianO Nov 30 '15 at 16:00
• @djechlin: I’m aware that all that matters is that the alphabet have at least two symbols, but the OP may not be. \\ In elementary courses you can’t assume that it’s $\{0,1\}$ even if you know that it’s a two-element alphabet: very often it’s $\{a,b\}$. – Brian M. Scott Nov 30 '15 at 16:02

If the alphabet has only one symbol then $L$ is regular, so assume the alphabet contains at least two symbols, which we'll call $0$ and $1$.
For $n>0$, let $w_n = (01)^n$ and $s_n = w_n w_n^R\in L$. Let $\sim$ be the equivalence relation of the Myhill-Nerode theorem: $$x\sim y \iff \forall z\,(xz\in L \leftrightarrow yz\in L).$$ By the theorem, $L$ is regular iff $\sim$ has only finitely many equivalence classes.
Suppose $m < n$, and let $z=w_m^R$. We have $w_m z = s_m \in L$. However, if $w_n z = (01)^n(10)^m \in L$, then by definition of $L$ there are $s,t$ with $|s|>0$ such that $$w_n z = (01)^n(10)^m = (01)^{n-m}(01)^m(10)^m = ss^Rt$$ But because $n>m$, there are no such $s$ and $t$, so $w_n z\notin L$ after all. So this $z$ distinguishes $w_m$ and $w_m$.
It follows that $$m\ne n \implies w_n \not\sim w_m,$$ so $\sim$ has infinitely many equivalence classes, hence $L$ is not regular.
• This keeps some of the previous answer (the use of $01$ and $10$), but Myhill-Nerode is a much better hammer to hit the problem with. – BrianO Nov 30 '15 at 19:31