2
$\begingroup$

Let $A = \{ uu \text{ } | \text{ } u \in \{a,b\}^* \}$ be a language. Suppose that we want to prove that A is not regular via the pumping lemma, why is the string w = $a^{p} a^{p}$ not valid to derive a contradiction?

$\endgroup$
2
$\begingroup$

The pumping lemma states that if a language $L$ is regular, then there exists a pumping length $p\gt0$ such that for all strings $s$ in $L$ with length at least $p$, there exists a way to split $s$ in the form $xyz$ such that all of the following are true:

  1. $xy^iz\in L$ for all $i\ge0,i\in\mathbb Z$
  2. $|y|\gt0$
  3. $|xy|\le p$

The contrapositive is:

For all pumping lengths $p\gt0$, if there exists a string $s$ in $L$ of length at least $p$ such that for all ways to split $s$ in the form $xyz$, at least one of the three statements (those mentioned above) are false, then the language $L$ is not regular.

When you prove that a language $L$ is not regular using the pumping lemma, you generally assume that it is regular, and prove that the premise of the contrapositive of the pumping lemma is true. This implies that the language is not regular, leading to a contradiction.

Now, in your problem, you would like to choose the string $a^pa^p$. As you can see in the contrapositive statement, the choice of choosing $x,y,z$ does not lie with you. So, you need to show that the contrapositive holds true for every choice of $x,y,z$, i.e., at least one of the three statements in the pumping lemma is false for every choice of $x,y,z$.

So, in general, $$a^pa^p=a^{2p}=a^ia^ja^k$$ for some $i,j,k\ge0$ and $i+j+k=2p$. Note that $j\gt0$ for statement 2 to be true, and $i+j\le p$ from statement 3.

Now, all that needs to happen is $j$ to be even and $i=k$,which, in general, is possible as all possible ways of splitting the string need to be taken into account that suppose $j=2l$ for some $l\gt0$. Then, $$a^pa^p=a^ia^{2l}a^i=a^{i+l}a^{i+l}$$

Now, as per statement 1, suppose we pump $y$, we get $a^i(a^{2l})^na^i\in L$ for all $n\ge0,n\in \mathbb Z$. Note that for every choice of $n$, $$a^{i+ln}a^{i+ln}\in L$$

So, for this string $s$, we have managed to find a way to split it, for any $p$, such that all the conditions of the pumping lemma hold. This does not show that the premise of the contrapositive is true, and hence does not lead to a contradiction. Thus, to show that it is not regular, you need to choose a more suitable string $s$ for all $p$ that results in the premise being true, which would imply that $L$ is not regular, leading to a contradiction.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

In this particular case you choose a string that only has a single letter $a$. That means any argument will also work for the restriction of $A$ to $\{a\}^*$, which is $\{ uu \mid u\in \{a\}^*\} = (aa)^*$. Now that is a regular language, which by the pumping lemma can be pumped within $(aa)^*$ and hence within $A$.

| cite | improve this answer | |
$\endgroup$

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.