# How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

How to show that the following language is not regular with the pumping lemma?

$$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$

• Possible duplicate of How to prove that a language is not regular? – David Richerby Nov 3 '18 at 10:06
• This seems like homework, what did you try, and where are you stuck? – Pål GD Nov 4 '18 at 22:37
• Did you consider accepting my answer? (This comment will be removed.) – John L. Apr 29 at 5:24

(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>2^d$$, $$m>2^d$$ and $$n\not=m$$, then $$\left|n\lceil\log_2n\rceil-m\lceil\log_2m\rceil\right| > 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?

• Hint for exercise 1, the pumping lemma for regular languages. – John L. Apr 29 at 5:27