# Examples of non-sparse languages

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.

• Do you know the definition of sparse? If so, what's stopping you produce examples yourself? – David Richerby Sep 7 '18 at 16:30
• Yes, but I am unable to design such an example which is non-sparse. – user730119 Sep 7 '18 at 16:39
• 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. – David Richerby Sep 7 '18 at 17:02
• 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. – user730119 Sep 7 '18 at 17:09

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.