0
$\begingroup$

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)?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I am afraid your argument is incorrect. When you pump, you will get $a^{n+ik}b^m$, and not $a^mba^mb$. $\endgroup$ – J.-E. Pin Jun 2 '17 at 9:20
  • $\begingroup$ 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$. $\endgroup$ – SivanBH Jun 2 '17 at 10:21
  • $\begingroup$ Are you sure that $w = a^nb^m$ as you wrote ? $\endgroup$ – J.-E. Pin Jun 2 '17 at 13:02
  • $\begingroup$ It looks like you want to consider the word $w = a^nba^{n + n!}b$ instead. $\endgroup$ – J.-E. Pin Jun 2 '17 at 17:08
  • $\begingroup$ Sorry, I considered $w$ as you wrote it just wrote it wrong in the answer. (Fixed it now) $\endgroup$ – SivanBH Jun 2 '17 at 19:13

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.