0

I have this problem:

  • $L_0 = L(a^*bba^*)$, the language of the regular expression $a^*bba^*$
  • $L_1 = \{uu \mid u \in L_0 \}$

Is $L_1$ a regular language?

I know that I should use the pumping theorem for this, but I don't know how to use it.

I assume that $L_1$ is the same as $a^*bba^*a^*bba^*$? Or am I wrong here too? So how do I know if this is a regular language?

martini
  • 84,101
rablentain
  • 645

1 Answers1

2

If we had $L_1 = L(a^*bba^*a^*bba^*)$, $L_1$ would (obviously) be regular, as generated by a regular expression. But note the difference: \begin{align*} L(a^*bba^*a^*bba^*) &= L_0 \circ L_0 = \{uv \mid u,v\in L_0\} \\ L_1 &= \{uu\mid u \in L_0\} \end{align*} The point in the definition of $L_1$ is that words of $L_1$ consits of two times the same word of $L_0$. Such languages are seldom regular, as a finite automaton cannot remember a whole word from $L_0$ to repeat it. This is only a handwaving argument, to prove that $L_1$ is not regular, you should, as you wrote, use the pumping lemma.

So, suppose $L_1$ were regular and $p$ its pumping length. Consider $w = a^pbba^pa^pbba^p \in L_1$. By the pumping lemma there would be a decomposition $w = xyz$ with $|xy| \le p$, $|y| \ge 1$. Then $y$ consitsts only of $a$s and $xy^iz = a^{p+i}bba^pa^pbba^p \not\in L_1$. So $L_1$ isn't regular.

martini
  • 84,101
  • The expression you pump can be simplified to $a^pbba^pbb$. Doesn't affect the argument, but making both $a^*$ use the same length might confuse people. – Peter Taylor Oct 14 '13 at 10:13