Class 8: More algorithms on machines


Reading
None.
Homework
Printout the homework and answer the questions on that paper.

Going over the homework
We went over the homework and arrived at the conclusion that Mystery Algorithm II from the last homework takes a machine M and a character x and produces a machine M' accepting exactly the strings accepted by M prefixed with the character x. This suggests the following thoerem about languages accepted by finite automata:
Theorem: If a language L ⊆ Σ* is accepted by a finite automaton then, for any character x ∈ Σ, the language { xw | w ∈ L } is also accepted by a finite automaton.
Proof? The mystery algorithm from the last homework actually constructs the finite automaton accepting L'.

Going a bit further ...
We talked about generalizing this to show that prefixing every element of a language accepted by a finite automaton with a fixed string produces a new language that is also accepted by a finite automaton. In other words:
Theorem: If a language L ⊆ Σ* is accepted by a finite automaton then, for any string v ∈ Σ*, the language { vw | w ∈ L } is also accepted by a finite automaton.
Proof: The following algorithm proves the theorem.
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!

Extending a machine's alphabet
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. 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.


Christopher W Brown
Last modified: Tue Sep 8 09:04:00 EDT 2009