Is the expression: L={w|w∈{a,b}*& ∃v:www=vv} is a regular language, and why?

Question

Is the expression: L={w|w∈{a,b}*&∃v:www=vv} a regular language?

If not, why?

Answer 1

It helps to come up with another characterisation of $L$.

Claim. $L = \{ uu : u \in \{ \mathtt{a}, \mathtt{b} \}^* \}$.

Proof. (⇒) If $w \in L$, write $w = x_0 \cdots x_{n-1}$. Then $$www = x_0 \cdots x_{n-1} x_0 \cdots x_{n-1} x_0 \cdots x_{n-1}.$$ This string has length $3n$, and so if $www = vv$, then $v$ must have length $\frac{3n}{2}$ (so $n$ must be even), and looking at the two halves of $www$ it must be that $$v = x_0 \cdots x_{n-1} x_0 \cdots x_{\frac{n}{2}-1} = x_{\frac{n}{2}} \cdots x_{n-1} x_0 \cdots x_{n-1} $$ So $x_0 = x_{\frac{n}{2}}$, $x_1 = x_{\frac{n}{2}+1}$, ..., $x_{\frac{n}{2}-1} = x_{n-1}$. If $u = x_0 \cdots x_{\frac{n}{2}-1}$ we have $w=uu$.

(⇐) If $w = uu$ for some $u \in \{ \mathtt{a}, \mathtt{b} \}^*$, then let $v = uuu$. Clearly $www = (uu)(uu)(uu) = uuuuuu = (uuu)(uuu) = vv$. So $w \in L$.

Using this claim we can show that $L$ is not regular by using the Pumping Lemma, taking for example the string $w=\mathtt{a}^p\mathtt{b}^p\mathtt{a}^p\mathtt{b}^p$ where $p$ is a supposed pumping length for $L$.