Input: Machine M = (Q, Σ, δ, s, W) and new symbol $ such that $ ∉ Σ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.
Output: Machine M' that accepts the same language as accepted by M, but which is defined for the alphabet Σ ∪ {$}
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