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.