I am trying to solve a pumping Lemma Problem where $L= \{(a^n)^n ; n\ge 0\}$ I am having a lot of trouble with the pumping lemma and understanding using it with different languages. Here is what I have so far and would appreciate any input on it.

Assume for contradiction that $L$ is a regular language. Since $L$ is infinite we can apply the pumping Lemma. Let $p$ be the critical length for $L$.

Let $w = (a^p)^p$ and length of $|w|>=p$. From the pumping lemma we can write $w = (a^p)^p = xyz$. With $|xy| \le p$ and $|y| \ge 1$. Thus $y = a^k, 1\le k\le p$. So for $xy^iz \in L$ we can take $xy^0z = xz = (a^{p-k})^p$ which should be contained in $L$ but since it is not we have a contradiction thus the language is not regular.

Any help or recommendations is appreciated, thank you.

  • 3
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Oct 4 '16 at 7:51
  • $\begingroup$ I don't see any question here. This is a question-and-answer site, so we expect you to formulate a specific question. You can ask about your approach, but you need to formulate a specific, narrowly focused question about it. "I would appreciate any input on [my approach]" is not specific enough to be a good fit here. $\endgroup$ – D.W. Oct 4 '16 at 18:50
  • $\begingroup$ See also cs.stackexchange.com/q/3075/755 $\endgroup$ – D.W. Oct 4 '16 at 18:50

You're on the right track. Here are a few missing details. First, note that $(a^n)^n=a^{n^2}$, so you want to prove that $L=\{a^{n^2}\mid n\ge 0\}$ isn't regular.

Assume $L$ is regular. Since $L$ is infinite, there's an integer $p$ for which the PL applies, so choose $s=a^{p^2}$ and write $s=xyz$ with $|xy|\le p$ and $|y|\ge 1$. Hence, $y=a^k$ with $1\le k\le p$. Then the PL implies that $xz\in L$. Thus we know that $|xz| =p^2-k$, [You goofed here.] and since $k\le p$, we have $$ |xz| =p^2-k\ge p^2-p >p^2-2p+1=(p-1)^2 $$ and so $(p-1)^2< |xz|<p^2$ and so $xz\notin L$, since $xz$ lies strictly between two adjacent (lengthwise) elements in $L$ and so can't be in $L$, a contradiction.

[The only way this could fail is if $-p\le -2p+1$ and that only holds when $p\le 1$ which we know must be true, since $p$ is the number of states of a FA that accepts $L$ and clearly a one-state FA won't recognize $L$.]

| cite | improve this answer | |
  • $\begingroup$ Should we close as duplicate? (cc @Evil) $\endgroup$ – Raphael Oct 4 '16 at 7:17
  • 1
    $\begingroup$ It is easier to consider the string $x y^2 z$, as there $\lvert x y^2 z \rvert = p^2 + \lvert y \rvert$, and $p^2 < p^2 + \lvert y \rvert \le p^2 + p < p^2 + 2 p + 1 = (p + 1)^2$, unconditionally. $\endgroup$ – vonbrand Feb 9 at 20:48
  • 1
    $\begingroup$ @vonbrand Right you are. It only took me a bit less than four years to see. $\endgroup$ – Rick Decker Feb 10 at 15:33
  • $\begingroup$ @RickDecker :-) $\endgroup$ – vonbrand Feb 14 at 13:56

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.