1
$\begingroup$

So I have a language: $$ L = \{a^{n^2} \mid n > 0\} $$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'm sort of doubting its validity.

So I take a pumping length $p$ such that a word $a^{p^2}$ can be split into 5 parts $uvxyz$. I need to assume that $L$ is context-free and run through some cases and check if the word violates the pumping lemma or if it doesn't violate the pumping lemma but isn't in the language definition.

I know the concept of proving languages aren't context free and the pumping lemma but I'm very stuck applying it to this particular language.

What do I do?

$\endgroup$
4
  • $\begingroup$ What happens when you "pump" that string of $n^2$ times $a$? How long can you make it by pumping? Can you pump it so that its length is no longer a square? $\endgroup$
    – chi
    May 13, 2016 at 13:12
  • 2
    $\begingroup$ Since all of $u,v,x,y,z$ consist entirely of $a$s, this is simple. Hint: show that $uv^ixy^iz$ has length greater than $p^2$ and less than $(p+1)^2$ for some suitable value of $i$. $\endgroup$ May 13, 2016 at 13:17
  • 1
    $\begingroup$ Possible duplicate of How to prove that a language is not context-free? $\endgroup$
    – DylanSp
    May 13, 2016 at 14:31
  • 2
    $\begingroup$ @DylanSp I don't think this is a duplicate. The asker is aware of the general techniques available but is asking about a specific attempt to prove that aspecific language isn't context-free. $\endgroup$ May 13, 2016 at 18:43

4 Answers 4

4
$\begingroup$

[Since (a) this is an instance of a standard problem and (b) I wasn't able to find it in the archives, I'll expand my comment into a hinted solution.]

As usual in problems like this, we assume that the language $L$ is context free, so the Pumping Lemma applies, meaning that there is an integer $p>0$ such that we can write the string $a^{p^2}$ as the concatenation of strings $uvxyz$ with $|vy|>0$ and $|vxy|=t\le p$. Hence, we'll have $$ 0 < |vy|=t\le p $$ This means that when we pump $uvxyz$ to $uv^ixy^iz$ we'll have $$ p^2<|uv^ixy^iz|=p^2+(i-1)t\le p^2+(i-1)p $$ Choosing $i=2$ gives us $$ p^2<|uv^2xy^2z|\le p^2+p $$ Now, in length order, the next string in $L$ after $a^{p^2}$ will be $a^{(p+1)^2}$. Here's the hint: use this fact to show that $uv^ixy^iz$ can't possibly be in $L$, contradicting the Pumping Lemma consequence that all the pumped strings are in $L$, so consequently $L$ cannot be a CFL.


This idiom, BTW, can be used to show that other languages over a one-symbol alphabet aren't context-free, like the $a^{n^5}$ language or the $a^p$ language, where $p$ ranges over the primes. There are more general results, as well, like the one that says that any CFL over a one-symbol language is regular. That, along with another theorem that says, roughly, that a regular language over a one-symbol language can't be too "sparse", gives a higher-level proof of your question.

$\endgroup$
1
$\begingroup$

If still have your question, I thought this might help why using pump up i=2 we can show the language is not Context Free.

Let $s=a^{p^2}$

next string is for (n+1) : $s=a^{(p+1)^2}$

$s=uvxyz$$; |vxy|\leq P$$;|vy|\geq1$

at most length $|vy|=p$ pump up i=2 so the pumped string $p^2+p$ which is not in the language because: $ (p+1)^2 $>$ (p^2+p)$ so the language given is not context-free.

$\endgroup$
0
0
$\begingroup$

A unary language (a language over a unary alphabet) is context-free iff it is regular. Moreover, such a language is context-free (or regular) iff the set of lengths of words in the language is eventually periodic.

The set $\{n^2 : n \in \mathbb{N}\}$ is not eventually periodic: the gap between adjacent elements increases without bound. So the language $\{a^{n^2} : n \in \mathbb{N}\}$ isn't regular or context-free.

$\endgroup$
0
$\begingroup$

Assume that the language $L = \{a^{(n^2)} | n > 0\}$ is context-free and let N be the pumping length given by the Pumping Lemma.

Choose the string $u = a^{(N^2)}$, which is in the language L. According to the Pumping Lemma, u can be decomposed into vwxyz such that |wxy| ≤ N, |wy| > 0, and $vw^mxy^mz$ is in L for every $m ≥ 0$.

When you choose m = 2, you pump the substring wxy, which increases the length of the string.

The length of the pumped string $vw^2xy^2z$ becomes $(N + n)^2$, where $n \in \mathbb{N}$. Now we now that |wy| = j + k, |w| = j, and |y| = k.

Now we know that this must be true $(N + n)^2 = N^2 + j+ k$.

From this equation, you deduce that $j + k = 2Nn + n^2$, which is greater than N since n > 0.

This contradicts the Pumping Lemma's requirement that |wxy| ≤ N.

Therefore, the assumption that L is context-free must be incorrect.Thus, you conclude that the language $L = \{a^{(n^2)} | n > 0\}$ is not context-free.

$\endgroup$
2
  • $\begingroup$ This proof attempt is seriously flawed. The length of $vw^mxy^mz$ is $N+(m-1)n$. One needs to find an $m$ such that $N+(m-1)n$ is not a square. $\endgroup$
    – Kai
    Aug 31, 2023 at 22:38
  • $\begingroup$ @kai You' re right, my bad, indeed the length of the pumped string is N+n , where n is a natural number. Now we have to prove that $N^2+j+k$ is not a square, but equivalently we can prove that $|wy|\geq N$ so the HP that $|wxy|\leq N$ is not satisfied. $\endgroup$
    – Dartypier
    Sep 1, 2023 at 11:14

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.