0

$\{a^{n^2}b^n|n\ge 0\}$
Is there any way to solve it beyond Pumping lemma ?

user220688
  • 509

1 Answers1

2

The pumping lemma will work. Show that if $r,s\ge 0$, and at least one of $r$ and $s$ is positive, then there is always a $k\ge 0$ such that

$$p^2+(k-1)r\ne\big(p+(k-1)s\big)^2\;.$$

Brian M. Scott
  • 616,228
  • The OP's question was though whether there was a way beyond Pumping lemma. However, the pumping lemma is sooo convenient ... – Hagen von Eitzen Jun 14 '15 at 21:21
  • @Hagen: The original question noted that the OP had tried to use both the pumping lemma and Ogden’s lemma without success. The OP immediately modified it to the present version, but in view of the original statement I take it that any proof will be acceptable. – Brian M. Scott Jun 14 '15 at 21:24