Proving a language is not regular Let 01 A string w of leng

Proving a language is not regular:

Let = {0,1}. A string w of length n= |w| is called sparse if every two 1s in the string have at least

log2 n 0s between them. Let L be the language of sparse strings. Show that L is not regular.

Solution

Assume that L is regular.

L = {10i1...0^j1}

where i and j are numbers greater than or equal to log₂n .

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 10ⁱ..10^j1 and 10ⁱ..0^k1 where j and k are greater than log₂n and j is not equal to k. So, they lead to the same state.

Hence, there is a contradiction.

Therefore, L is not regular.