Let L be the language on = {0, 1} consisting of words that end in either 01 or 10 and contain neither 010 nor 101 as a substring.

(a) Find a DFA A that recognises (accepts) L. Six states will be sufficient. Label the initial state S, other non-accepting states T, U, . . ., and accepting states X, Y, . . ..

(b) Find a regular expression R for the language L. Do this by applying the eliminating vertices algorithm (described in lectures and the course notes) to your automaton A from Question 1. Its OK to compress several steps into one.

(c) Show how 0111001100001 matches your R of (b).

(d) Show why 101 does not match your R of (b)