Let language L = {w ∈ {0, 1}∗ | w contains the substring 0⌈ |w|2 ⌉}. In other words, a string in L must contain a consecutive subsequence of 0’s that is at least 12 as long as the string itself.
For example, the following strings are in L: {ε, 0, 1001, 0011, 1011000000}.
The following strings are all not in L: {1, 101, 00101, 0001000}.
Suppose you are trying to prove that L is not regular using the pumping lemma.
Your proof starts (correctly) like this:
Suppose for a contradiction that L is regular. Let p be the pumping length given by the
pumping lemma.
Now you have to choose string s. For each choice of s below, state whether or not this choice of s can be used to finish the proof that L is not regular. If your answer is YES you do not have to explain anything. If your answer is NO, you should also
briefly explain why it cannot be used (including, if appropriate, specifying a valid decomposition for which all pumped versions of the string remain in the language).
(a) s = 0p1p
(b) s = 1p0p
(c) s = 1p0p−1
(d) s = 1p−10p
(e) s = 0p+11
(f) s = 1001
(g) s = 0p+11p
(h) s = 1p0p+1