1
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hint for exercise 1, the pumping lemma for regular languages. $\endgroup$ – John L. Apr 29 at 5:27

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.