# Prove that L = { wu; wu in {a,b}* and |w| = |u| } is not regular

Prove that $L = \{wu, wu \in \{a,b\}^* \ \land |w| = |u| \}$ is not regular.

I'm trying to approach this problem with the pumping lemma.

So I know I have to pick a string s, which can be split into xyz components in terms of the pumping length, p.

But I cannot seem to find an s.

For example using $s = a^p b^p$ or $s = a^p a b^p b$, since $|xy| \le p \land |y| > 0$, then y must contain some a's. So we can try to pump $x y^i z$ to see the new string is still in L.

The issue is that if y contains an even number of a's it can always be pumped because the resulting string will have even length so w can be the first half and u be the second half.

• Without some more specifications on $w$ and $u$, this is a regular language. It consists of all even-length strings over $\{a,b\}$. Commented Nov 18, 2016 at 20:53
• @RickDecker Yes, those were my initial thoughts. I had this question on an exam. So the language wouldn't be any different to { $w, w \in \{a,b \}^* \land |w|$ is even } Commented Nov 18, 2016 at 21:07
• Yup. Exactly right. Commented Nov 19, 2016 at 2:44

As Rick Decker said $L$ is a regular language. For example: $$L= \mathscr{L}(\,(aa | ab | ba | bb)^*\,)$$
If your teacher asked you to prove that $L$ is not regular in an exam then he is a big troll. Otherwise remember that the pumping lemma is only usefull to prove that a language is not regular and if you fail to find the contradiction in the lemma then that doesn't prove anything. $L$ can be regular or irregular at that point.