1. (50 point) For i=1, 2, 3, 4 and 5, design NFAs Ni , such that L(Ni) = Bi , where:

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

(b) B2 = {w | every odd position of w is 1}. Note: 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) B3 = {w | all strings except the empty string and the string 11}.

(d) B4 = {0} with two states.

(e) B5 = 0 1 1 + with three states.