Answer all questions. Unless otherwise stated, all the DFAs and NFAs in this question use = {0, 1} as the alphabet.

1. (50 point) For each i=1, 2, 3, 4 and 5, design a NFAs N_i , such that L(N_i)= B_i , where:

(a) B₁ = {w | w has an even number of 00 s, or, contains exactly two 10 s}.

(b) B₂ = {w | every odd position of w is 1}. Remark: In this question, we use the following convention: the position of a string w starts with position 0. For example, If s is the string 010, then the symbol at position 0 (resp. 1, 2) of s is 0 (resp. 1, 0) respectively. Hence, s will be in B2. In addition, we will consider the empty string e 6 B2.

(c) B₃ = {w | all strings except the empty string and the string 11}.

(d) B₄ = {0} with two states.

(e) B₅ = 0 1 1 + with three states.

Your answer should provide, for each NFA, a finite state diagram where all the states, the starting state, all of the accepting states and all the transitions (with the corresponding labels) are displayed/drawn clearly. Show intermediate step(s) when applicable.