Proof that a given language is not context-free

Question

Given the language $L = \{w \in \{a,b\}^* \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ and the assignement to proof that $L \notin CFL$ with the Pumping lemma.

Assuming $L \in CFL$, would it be possible to start with defining a language $L' := L \cap a^+$ which has to be context-free since $CFL$ is closed under intersection with $REG$. Now I would have to proof that $L' = \{w \in a^+ \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ isn't regular because the alphabet contains only one symbol.

Let $k$ be the constant of the Pumping lemma and $m > k$ and $m > 42$. So $z = a^{m^2\cdot\sqrt{m^2}} = a^{m^3} \in L'$.

$|z| = |uvw| = m^3 ...$

How to continue?

Answer 1

You're off to a good start. You recognize that all you have to do is show that the language $L'$ isn't regular. You let $k$ be the integer of the PL and choose an integer $m$ with $m>k$ and $m>42$ so you choose to pump the string $z=a^{m^3}$. Write this as $uvw$ with $|v|=t$ and $0<t<k$. Now we'll have $|uv^2w|=m^3+t<m^3+m$. This string can't be in $L'$ since it's strictly smaller than the next largest string in $L'$, namely the one with length $(m+1)^3$, since obviously $$ m^3+m<m^3+3m^2+3m+1 $$ Since $L'$ isn't regular, $L$ can't be a CFL.

Answer 2

Use the pumping lemma for CFLs. Let N be the pumping lemma's constant, and take $\sigma = a^{N^{3/2}}$, which certainly has $\lvert \sigma \rvert \ge N$. So we can write $\sigma = v w x y z$ with $\lvert w x y \rvert \le N$ and $w y \ne \epsilon$ such that for all $k \ge 0$ we have $v w^k x y^k z \in L$.

But here only lengths matter. Call $u = \lvert w y \rvert$, so that the length of the pumped string is:

$\begin{align} \lvert v w^k x y^k z \rvert = N^{3/2} + (k - 1) u \end{align}$

where we know that $u \le N$.

Now look for $n$ such that $(n + 1)^{3/2} - n^{3/2} > N$. By the binomial theorem:

$\begin{align} (n + 1)^{3/2} - n^{3/2} &= n^{3/2} \left( (1 + 1/n)^{3/2} - 1 \right) \\ &= n^{3/2} \left( 1 + \frac{3}{2 n} + \dotsb - 1 \right) \\ &\ge \frac{3 \sqrt{n}}{2} \\ & > N \end{align}$

This is $n > 4 N^2 / 9$. This provides a stride larger than $N$ between lengths of strings in the language, the pumped string will fall short.

Answer 3

For any context-free language $L$, the set $S$ of lengths of words in $L$ is eventually periodic, that is there exists an $m>0$ such that $x \in S$ iff $x + m \in S$ (this is one form of Parikh's theorem). In your case, if $L$ were linear then $S = \{ k^3 : k^2 \geq 42 \}$ would be eventually periodic. However, an eventually periodic set is either finite or has positive density, whereas this set $S$ is neither.

A more general form of Parikh's theorem states that the set of histograms of words in a context-free language (the histogram of a word counts how many times each symbol appears in it) is semi-linear, which is a union of linear sets, a linear set being a set of the form $\{ x + n_1 y_1 + \cdots + n_r y_r : n_1,\ldots,n_r \in \mathbb{N} \}$, where $x,y_1,\ldots,y_r \in \mathbb{N}^\Sigma$. This is useful for proving that languages defined using more complicated constraints are not context-free.