Proving non-regularity of $u u^R v$?

This particular language:

$$L = \{ u u^R v \,:\, u, v \in \{0, 1\}^+\}$$

is giving me a lot of trouble.
I highly suspect that its non-regular, considering that $\{ u u^R : u \in \{0, 1\}^+\}$ is non-regular, and I can't seem to reason out a DFA for it.

However, trying to achieve a contradiction with the pumping lemma is giving me a lot of trouble. because of the arbitrary $v$ in the construction.
In particular, if the string starts with $00$ or $11$ it is automatically in the language because we can pick $v$ as the remainder and the first two characters are trivially the reverse of each other.

Issues like this seem to thwart my every attempt at applying the pumping lemma. With $p$ as the pumping length, I tried something like $(01)^p (10)^p 1$ but you can simply pump up the starting character to obtain a string that starts with $00$ (and pumping down also works), so this string doesn't work for contradicting the pumping lemma.

I'm pretty stuck on ideas for strings that will contradict the pumping lemma, so I could appreciate a hint on the problem. (Perhaps it is regular? That's still in the back of my mind too)

When you are stuck in a place like this, it pays to check if the method can work at all. That is, try to prove the opposite. Since the Pumping lemma does not characterise REG, this is actually possible.

Claim: Your language $L$ fulfills the conditions of the Pumping lemma with $p=1$.

Let $w = uu^Rv$ for $u, v \in \Sigma^+$; say $|w|=n$ and $|u|=m$. With the (canonical) notation from the Pumping lemma, pick $x = \varepsilon$, $y=w_1$ and $z = w_2\cdots w_n$.

By definition, $|y| \geq 1$ and $|xy| \leq p$. Furthermore,

• $xy^0z = (u_2\cdots u_m) \cdot (u_2\cdots u_m)^R \cdot u_1 v \in L$,

• $xyz = w \in L$, and

• $xy^iz = u_1 u_1^R (u_2 \cdots u_m) u^R v \in L$, for $i \geq 2$.

Q.e.d. -- $L$ has the Pumping property.

That is, the Pumping lemma can not be used here, you need other methods.

StackExchange Computer Science Q#48186, answer score: 5