2
$\begingroup$

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.

$\endgroup$
3
  • 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$ Commented Oct 4, 2016 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.
    Commented Oct 4, 2016 at 18:50
  • $\begingroup$ See also cs.stackexchange.com/q/3075/755 $\endgroup$
    – D.W.
    Commented Oct 4, 2016 at 18:50

1 Answer 1

6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Should we close as duplicate? (cc @Evil) $\endgroup$
    – Raphael
    Commented Oct 4, 2016 at 7:17
  • 2
    $\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
    Commented Feb 9, 2020 at 20:48
  • 1
    $\begingroup$ @vonbrand Right you are. It only took me a bit less than four years to see. $\endgroup$ Commented Feb 10, 2020 at 15:33
  • $\begingroup$ @RickDecker :-) $\endgroup$
    – vonbrand
    Commented Feb 14, 2020 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.