Prove that, "For each even number n greater than 2, there exists a 3-regular graph with n nodes." (5 Marks)

(3 x 5 Marks)

Draw the state diagram for the DFAs that accept the following languages [in all of the problems, E = {a, b}]: i. ii. iii. {wl w is any string that does NOT contain exactly two a's} {w w begins with an 'a' and ends with 'ab'} {w/ w does NOT contain the substring aab}