# Nontrivial examples of sparse languages

A language $L$ is said to be sparse if there exist a polynomial $p$ such that $|L \cap \{0,1\}^n| \le p(n)$.

One trivial example is suppose language is over single alphabet $1$ then $$L = \{1^n | n \in Z^+\}$$

Question : What are the other non-trivial examples of sparse languages?

• I don't really understand what you're looking for. Any class that meets the definition is an example, so what's stopping you from generating your own examples? Sep 7 '18 at 16:33

However, since $\{0,1\}^*$ has exponential growth, you need to be able to derive some kind of combinatorial property from the language definition. For example, let $k$ be a constant and consider the following language:
$\qquad L = \{x \mid x \text{ contains$k$ones}\}$
$L$ is sparse, the key observation being that $\binom{n}{k}$ for a fixed $k$ is a polynomial in $n$.