# exercise 1.49

### a. Theorem

Let B = {1ky|y∈{0,1}* and y contains at least k 1s, for k ≥ 1}. Show that B is a regular language.

### a. Proof

B equals to "Let B is a string that begins with 1 and, after, contains at least another 1".

This DFA doesn't "count" the number of 1s

### b. Theorem

Let B = {1ky|y∈{0,1}* and y contains at most k 1s, for k ≥ 1}. Show that B is not a regular language.

### b. Proof

As shown in 1.77 Sipser's example, we can apply an absurd proof of the pumping lemma to this language

Let we assume that B is regular. Let we choose one 1 as pumping's y and the second part (i.e. from the first 0 found) as pumping's z, and it seems to work:

$\underset{y}{\underset{⏟}{1111}}\underset{z}{\underset{⏟}{0100}}$

or better

$\underset{{y}_{1}}{\underset{⏟}{1}}\underset{{y}_{2}}{\underset{⏟}{1}}\underset{{y}_{3}}{\underset{⏟}{1}}\underset{{y}_{n}}{\underset{⏟}{1}}\underset{z}{\underset{⏟}{0100}}$

Pumping lemma doesn't allows a length of 0 for the y part, but allows that y is repeated zero times.

Using as example the previous string, with y repeated zero times, we obtain the string 0100, that doesn't match. Thus we obtain a contradiction.