Class 7: Algorithms on machines

Printout the homework and answer the questions on that paper.

Remember ...
We've spent a class and a half talking about algorithms for machines - the complement, intersection and union algorithms being our examples. These algorithms are so important, because they're proofs about properties of the languages accepted by machines. This class will be full of such algorithms, so we went through an excercise designed to help you make sure you understand our mathematical language for specifying algorithms. Our excercise was ...

Mystery Algorithm I
Let Σ be an alphabet. Here's the Mystery Algorithm:

Input: alphabet Σ and w ∈ Σ*, where w =
Output: ({0,1,...,n+1},Σ,δ,1,{n+1}), where

δ:{0,1,...,n+1} x Σ &rarr {0,1,...,n+1}
δ(k,x) = { k+1 if 0 < k ≤ n and x = ak
0 otherwise

Try following this algorithm by giving it input Σ = {b,c} and w = cbb, and seeing what 5-tuple it produces. Now, take this 5-tuple and translate it into a diagram for the machine. Can you figure out what the Mystery Algorithm does?

Answer: For the example input the algorithm produces a machine that accepts only the string cbb. In general, the algorithm produces a machine over the alphabet Σ that accepts the language {w}.

So What?
Does this algorithm prove anything to you about what kinds of languages are accepted by finite automata? Yes! We've just proven that for any string, the language consisting solely of that string can be accepted by a finite automaton!
Theorem: For any string w ∈ Σ*, there is some DFA accepting the language {w}.

The proof, of course, is the Mystery Algorithm. This theorem may not impress you so much. Very well. What's interesting is not so much this theorem/algorithm, but what happens when we combine it with our other theorems/algorithms. This is just like programming: combining functions is really powerful. The following theorem, which I hope is interesting to you, combines the union and mystey algorithms. Let's rename the Mystery Algorithm OneString(Σ,w) and refer to the union algorithm from the previous homework as Union(M1,M2).

Theorem: For any finite set of strings S = {w1, w2, ..., wn} ⊆ Σ* there is a DFA accepting S.
Proof: The following algorithm constructs a DFA accepting S, thus proving the theorem:
Algorithm SetStrings
Input: alphabet Σ, finite set of strings S = {w1, w2, ..., wn} ⊆ Σ*
Output: machine M such that L(M) = S, where
M = ({0},Σ,δ(k,x) = 0,0,{ }) if S = { }
M = Union(OneString(Σ,w1),SetStrings(Σ,S - {w1})) otherwise.

Of course, technically, to be complete we ought to prove that this algorithm really does what we claim it does. However, hopefully the way it works is clear enough to you that you are conviced without a formal proof. In any event, we'll need a little more formal machinery before we can prove the correctness of algorithms like this.

This result, i.e. that every finite language is accepted by some finite automaton, is important. Of course we should keep in mind that there are also many infinite languages that are accepted by finite automaton, so this result is by no means the last word on the subject of languages accepted by finite automata!

Christopher W Brown
Last modified: Tue Sep 8 08:56:36 EDT 2009