Proving non-regular language using the pumping lemma

Question

I would like to verify that the following language is not regular.

I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in fact regular if the pumping lemma is valid)

So, given the following language,

$\Sigma =\{a,b\}$, $L=\{v\cdot u\cdot u: v,u\in\Sigma^*,u\neq \varepsilon\}$

Can I show that the pumping lemma is not valid here?

Side note:

I think I can prove that this language is regular by using regular expressions like so:

denote $r= (a\cup b)^*$ now, $L=(a\cup b)^*\cdot (aa\cup bb)\cdot r\cdot r$

Is this true?

Answer 1

Your language is not regular. Indeed, let $n$ be the pumping lemma constant, and consider the word $ab^nab^na = a(b^na)^2 \in L$. Suppose that your language were regular. Then you could write $ab^nab^na = xyz$, where $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. We consider two cases:

• Case 1: $x = \epsilon$, and so $y = ab^t$ for some $t \geq 0$. Then $xy^0z = b^{n-t}ab^na$. Suppose this were of the form $vu^2$. Considering the second copy of $u$, we see that $u$ ends in $a$. Since there are two copies of $a$, necessarily $u = b^na$. This is only possible if $t = 0$ (which is OK) and $v \neq \epsilon$ (which is not OK).

• Case 2: $x = ab^t$, and so $y = b^s$ for some $t \geq 0$ and $s \geq 1$. Then $xy^0z = ab^{n-s}ab^na$. Suppose this were of the form $vu^2$. Since $v \neq \epsilon$, the word $u^2$ is a suffix of $b^{n-s}ab^na$, and so as before, necessarily $u = b^na$ and we reach a contradiction since $s \neq 0$.

Now, why does your regular expression $(a+b)^* (aa+bb) (a+b)^* (a+b)^*$ not work? You are implicitly assuming that if you write "$r \cdot r$" then the semantics are that the same word must be chosen twice. However, this need not be the case. For example, the word $aab$ matches your regular expression, but is not in $L$.

Answer 2

Given the word $w = ab^p ab^p$, clearly $w\in L \land |w|=2\cdot(p+1)\geq p$.

Now, consider the division $w=xyz$ where $|xy|\leq p \land |y|>0$ then

• Case 1: $x=\varepsilon$, $\forall s\geq0\ ,y=ab^s$ then if $i=0$ we get that $xy^0z$ is actually $b^{p-s}ab^p$ and that's clearly not in L, because of the '$a$' in the middle of the new word.

• Case 2: $x\not=\varepsilon$ then $\forall s>0:\ y=b^s$ then again if $i=0$ we get that $xy^0z = ab^{p-s}ab^p$ and because $s>0$ then there is not a repeatable word (because $u=ab^p$ or $u=ab^{p-s}$) so we can conclude that $w\notin L$.

Thus $L\notin REG$.