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\}.$$


(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?


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.