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.
