How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?
(Dense-length lemma for regular languages) Let $R$ be an regular language that has infinitely many words. Then there exists a number $d$ such that for any word in $R$, there is another word such that the difference of the lengths of both words is less than $d$.

The above lemma says, basically, the lengths of words in a regular language cannot be too sparse anywhere. It can be proved easily using the pumping lemma for regular languages.

Let us take a look at $L$. The lengths of its word are $\{n\lceil\log_2 n\rceil \,\mid n\in \Bbb{N}-\{0\}\}$. When $n$ goes larger and larger, the lengths become sparser and sparser because of the factor $\lceil\log_2n\rceil$. In fact, if $n&gt;2^d$, $m&gt;2^d$ and $n\not=m$, then $\left|n\lceil\log_2n\rceil-m\lceil\log_2m\rceil\right| &gt; d$. So $L$ cannot be regular because of the above lemma. 



Exercise 1. Prove the dense-length lemma for regular languages.

Exercise 2. Prove the dense-length lemma also holds for context-free languages that have infinitely many words.

Exercise 3. Does the dense-length lemma hold for context-sensitive languages?