Class 8: More algorithms on machines


Reading
None.
Homework
Write an algorithm with the following specification:
Input: Machine M = (Q, Σ, δ, s, W) and new symbol $ such that $ ∉ Σ
Output: Machine M' that accepts the same language as accepted by M, but which is defined for the alphabet Σ ∪ {$}
Your solution should be a mathematical description of the algorithm in the same syntax as our other algorithms, including the one below. I know this might seem a little pointless, but I promise you it's not. Suppose you have a machine M that's defined over alphabet {a,b}, and you want to use the mystery algorithm from last class's homework to construct a machine that adds the character c to the front of every string of everything accepted by M. The mystery algorithm won't apply, because c is not part of the alphabet of M. However, you could first use a solution to this homework to extend the alphabet of the machine to include c, and then apply the mystery algorithm. So, a solution to this homework helps in gluing other algorithms together.

An algorithm for creating a machine M' s.t. L(M') = L(M) ∪ {e}
We could, of course, use our algorithm for union along with a simple 2-state machine accepting the language {e}, but I want a direct algorithm. Your algorithm should create a machine with just one more state than the original!

Consider the machine M3:

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

Solution:

M' = (Q ∪ {$}, Σ, δ', $, W ∪ {$}), where
δ: (Q ∪ {$}) x Σ → Q ∪ {$}
δ'(q,y) = { δ'(s,y) if q = $
δ(q,y) otherwise


Christopher W Brown
Last modified: Mon Sep 8 13:37:49 EDT 2003