2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ... and particularly useful for languages over a one-symbol alphabet. $\endgroup$ – Rick Decker Oct 14 '15 at 23:51

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.