Let 0 1 A string w of length n w is called sparse if e

Let ? = {0, 1}. A string w ? ? ? of length n = |w| is called sparse if every two 1s in the string have at least dlog2 ne 0s between them. Let LS ? ? ? be the language of sparse strings. Show that LS is not regular.

Solution

Assume that L is regular.

L = {10i1...0j1}

Where i and j are numbers greater than or equal to log2n

Using Pigeonhole principle:

Pigeons = all strings in L.

Holes = states

Put pigeon string into hole corresponding to the state it leads to.

Using the pigeonhole principle, two pigeons share a hole, say 10i..10j1 and 10i..0k1 where j and k are greater than log2n and j is not equal to k. So, they lead to the same state.

Hence, there is a contradiction.

Therefore, L is not regular.