6
$\begingroup$

Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to substitute each $S$ with sequence of $S$'s of length $n$.

$\endgroup$
  • 2
    $\begingroup$ Yes, for instance the finite language {aaaa, aaab, aaaaaaaaa, aaaaaaaab} contains words of length $2^2$ and $3^2$. $\endgroup$ – immibis Jun 27 '16 at 0:44
  • 1
    $\begingroup$ Please edit the question to clarify what you're asking. I can see multiple ways to parse what you've written. Do you mean that every word in the language must have a length that is a perfect square or perfect cube? That at least one word must have such a length? Must the language be infinite? Do you want a single language where lengths are squares or cubes, or are you asking if there's a language whose lengths are squares or a language whose lengths are cubes? Or something else entirely? $\endgroup$ – David Richerby Jun 27 '16 at 12:09
10
$\begingroup$

For a language $L$, let $N(L) = \{|w| : w \in L\}$, and let $U(L) = \{1^n : n \in N(L)\}$. Parikh's theorem shows that if $L$ is context-free then $U(L)$ is regular. In particular, since $\{1^{n^2} : n \geq 0 \}$ is not regular, no context-free language $L$ satisfies $N(L) = \{n^2 : n \geq 0\}$. In fact, no infinite context-free language $L$ even satisfies $N(L) \subseteq \{n^2 : n \geq 0\}$ (exercise).

$\endgroup$
4
$\begingroup$

Yuval's answer uses Parikh's theorem to show that if L is context-free then U(L) is regular, and then (implicitly) the pumping lemma for regular languages to show that U(L) is not regular.

The use of Parikh's theorem can be avoided using the pumping lemma for context-free languages.

If $L$ is infinite and context-free, then there is a word $uvwxy$ with $|vx|>0$ such that $uv^kwx^ky \in L$ for all $k \ge 0$. So, $|uwy|+k|vx| \in N(L)$ for all $k$. Since $|vx| \ge 0$, this is an infinite arithmetic progression. In general, if $L$ is infinite, then $N(L)$ contains an infinite arithmetic progression (this is weaker than what we get from Parikh's theorem, which gives us that $N(L)$ is entirely made up of a finite union of arithmetic progressions).

The set $\{n^c : n\ge 0\}$ contains no infinite arithmetic progression when $c>1$. Note that the gap between $n^c$ and $(n+1)^c$ grows to infinity, so at some point it must be larger than any given $b$, so if $a+kb= n^c$, then $n^c < a+(k+1)b < (n+1)^c$ for large enough $n$, so $\{a+kb :k\ge0\} \not\subseteq \{n^c:n\ge 0\}$.

$\endgroup$
  • 1
    $\begingroup$ So that would rule out any polynomial with degree ≥ 2 as well, plus any other function that grows more than linear. $\endgroup$ – gnasher729 Jun 27 '16 at 10:15

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.