Algorithm PrefixString
Input: machine M = (Q, Σ, δ, s, W), string v ∈ Σ*, where v = v1 v2 ... vk
Output: machine M' such that L(M') = { vw | w ∈ L(M) }, where
M' = M if v = λ
M' = MysteryAlgorithmII(PrefixString(M,v2v3...vk), v1) otherwise.
Of course we really ought to prove that the algorithm PrefixString does what we say it does, but once again: a) hopefully it's so obvious that it works that you don't require further convincing, and b) we don't have all the formal tools in place to prove such a thing --- though we will soon, I promise!
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. 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 problem in order to extend the alphabet of the machine to include c, and then apply the mystery algorithm. So, a solution to this problem 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 Σ ∪ {$}