0
$\begingroup$

All I could find is an example of sparse language.

I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the languages string generation is bound to at least one polynomial, so I am unable to design a language L whose strings are not bounded to a polynomial function.

$\endgroup$
  • 1
    $\begingroup$ Do you know the definition of sparse? If so, what's stopping you produce examples yourself? $\endgroup$ – David Richerby Sep 7 '18 at 16:30
  • $\begingroup$ Yes, but I am unable to design such an example which is non-sparse. $\endgroup$ – user730119 Sep 7 '18 at 16:39
  • $\begingroup$ What did you try? Why didn't it work? Was the problem in thinking of a language that might be non-sparse or proving that it's really non-sparse? Do you know any functions that grow faster than all polynomials? It's hard to pitch an answer at the right level without knowing where you're at. $\endgroup$ – David Richerby Sep 7 '18 at 17:02
  • $\begingroup$ I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the languages string generation is bound to at least one polynomial function. $\endgroup$ – user730119 Sep 7 '18 at 17:09
1
$\begingroup$

For a language $L$, let's write $\|L\|_n$ for the number of length-$n$ strings it contains. So $L$ is sparse if there is a polynomial $p$ such that $\|L\|_n\leq p(n)$ for all $n$. The key point is that, for a language to be sparse, we must be able to pick just one polynomial that works for all $n$: you're not allowed to use a different polynomial for each $n$.

For example, suppose that you wanted to prove that the language of strings over $\{0,1\}$ with at most two $1$s is sparse. You can't say "Well, for $n=3$, there are seven valid strings, and $7 < n+5$ for $n=3$. And for $n=4$, there are eleven valid strings, and $11 < n^2-4$ for $n=4$, and..." You have to pick just one polynomial that works for all values of $n$: in this case, $n^2$ works, so the language is sparse.

So, for a non-sparse language, $\|L\|_n$, when considered as a function of $n$, must grow faster than any possible polynomial. The simplest examples of functions that grow faster than polynomials are exponentials. Conveniently, $\{0,1\}^*$ has $\|\{0,1\}^*\|_n=2^n$ for all $n$. So, whatever polynomial $p$ you pick, $\|\{0,1\}^*\|_n>p(n)$ for all large enough $n$. Therefore, $\{0,1\}^*$ is not sparse.

Another example of a non-sparse language is the complement of a sparse language. If $\|L\|_n\leq p(n)$ for all $n$, then $\|\overline{L}\|_n\geq 2^n-p(n)$ and this grows faster than any polynomial if $p$ is a polynomial.

$\endgroup$

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.