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.

  • 2
    $\begingroup$ Without some more specifications on $w$ and $u$, this is a regular language. It consists of all even-length strings over $\{a,b\}$. $\endgroup$ – Rick Decker Nov 18 '16 at 20:53
  • $\begingroup$ @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 } $\endgroup$ – lambda Nov 18 '16 at 21:07
  • $\begingroup$ Yup. Exactly right. $\endgroup$ – Rick Decker Nov 19 '16 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.

In this answer I covered some common mistakes when students use the pumping lemma: Common Mistakes


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.