# Does$\{w\in\Sigma^*=\{a,b\}^*: \nexists u\in \Sigma^*, w=uu\}$ uphold the pumping lemma

I have the $L=\{w\in\Sigma^*=\{a,b\}^*: \nexists u\in \Sigma^*, w=uu\}$.

Does it uphold the pumping lemma (regardless of it being regular or otherwise)?

## 1 Answer

Apparently it does not. Proof:

For every $n>0$ we can choose the word $w=a^nba^mb$ where $m=n+n!$ ($n\neq m$). Which ever way we split $w$ into $w=xyz$ (such that $|xy|\leq n, |y|>0$) it must be that $y$ is a sequence of $k$ $a$'s where $k\leq n$, thereforewe can always choose to pump $y$ $i$ times, where $n-k+ik=m\Rightarrow i=(m-n+k)/k=n!/k+1$ and since $k\leq n$ we know this number is in $\mathbb N$, hence $xy^iz=a^mba^mb\notin L$.

• I am afraid your argument is incorrect. When you pump, you will get $a^{n+ik}b^m$, and not $a^mba^mb$. – J.-E. Pin Jun 2 '17 at 9:20
• Pretty sure that's not true. The entire $xy$ is contained within the $a^n$ section (since $|xy|\leq n$), so at the very least, after pumping, I will have $a^pba^mb$, and all I need to prove is that $p=m$. And it is: taking the $y$ out of the word (by setting $i=0$) I get $a^(n-k)ba^mb$. Now for every increment of $i$ i get $k$ more $a$'s, so I have $a^(n-k+ik)ba^mb$. – SivanBH Jun 2 '17 at 10:21
• Are you sure that $w = a^nb^m$ as you wrote ? – J.-E. Pin Jun 2 '17 at 13:02
• It looks like you want to consider the word $w = a^nba^{n + n!}b$ instead. – J.-E. Pin Jun 2 '17 at 17:08
• Sorry, I considered $w$ as you wrote it just wrote it wrong in the answer. (Fixed it now) – SivanBH Jun 2 '17 at 19:13