Let = {0, 1}. Let F be the language of all strings over that do not contain a pair of 1s that are separated by an odd number of symbols: that is, the number of symbols in the middle between any pair of 1s cannot be 1, 3, 5, etc.

(a) Give at least 3 examples of strings in F.

(b) Let G be the complement of F; that is, G = F. Describe G, and give some examples of strings in G.

(c) Find an NFA N that accepts G. Give both the state diagram and the formal description as a 5-tuple.

(d) Convert N to a DFA M. You only need to give the state diagram.

(e) Find a DFA M which accepts F. You only need to give the state diagram.