1. 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 recognizes (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. It’s
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).
2. Let M be the language determined by the regular expression
E = (0 + 1)(00 ∗ 0 + 11 ∗ 1) ∗ (0 + 1).
(a) Prove M ≠L by giving a string belonging to one language but not the other.
(b) Construct an automaton (DFA) that recognizes (accepts) M. Do this by applying the algorithm
(described in lectures and the course notes) that first ‘expands’ E to an NFA with all ε-arrows
absorbed, and then converts this to a DFA.