Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Write an algorithm that takes a machine M and creates a machine M' such that L(M') = L(M) ∪ { λ }. (Recall: λ is the empty string.)

We could, of course, just use our algorithm for union along with a simple 2-state machine accepting the language { λ }, but I want a direct algorithm. Your algorithm should create a machine with just one more state than the original!

Hint: Consider the machine M3:

This machine accepts the language of all strings over {a,b,c} that contain the substring ac or end in a. Suppose we wanted to add the empty string to this language? How would you construct a machine M4 that accepts this new language? (Note: just making q0 an accepting state won't cut it! Do you see why?) Now, can you transform the technique you applied to machine M3 into a general technique for creating a machine accepting L(M)∪{ λ } that works for any machine M?

Your solution should be a mathematical description of the algorithm in the same syntax as our algorithms for complement and intersection, the mystery algorithm from last homework, and the algorithms from class.

Problem 2

Draw the machine produced by your Problem 1 algorithm for the input machine below. Note: Follow what your algorithm does, not what you want it to do.