**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.*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*Σ ∪ {$}**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