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. Here in the
notes we will write those down explicitly:
If $L$ is a language that is accepted by some finite
automaton, then the language $\overline{L}$ is accepted by
some finite automaton.
Let $M$ be a finite automaton accepting language $L$,
i.e. $L(M) = L$. Running
"the complement algorithm" from the previous class
produces finite automaton $M'$ such that
$L(M') = \overline{L(M)} = \overline{L}$.
If $L_1$ and $L_2$ are languages that are accepted by finite
automata, then the language $L_1 \cap L_2$ is accepted by
some finite automaton.
Let $M_1$ and $M_2$ be finite automata such that
$L(M_1) = L_1$ and $L(M_2) = L_2$. Running
"the intersection algorithm" from the previous class
produces finite automaton $M$ such that
$L(M) = L(M_1) \cap L(M_2) = L_1 \cap L_2$.
If $L_1$ and $L_2$ are languages that are accepted by finite
automata, then the language $L_1 \cup L_2$ is accepted by
some finite automaton.
Let $M_1$ and $M_2$ be finite automata such that
$L(M_1) = L_1$ and $L(M_2) = L_2$. Running
"the union algorithm" from the previous class's homework
produces finite automaton $M$ such that
$L(M) = L(M_1) \cup L(M_2) = L_1 \cup L_2$.
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 ...
ACTIVITY: Mystery Algorithm I
Break up into groups of three, find a whiteboard, and do the
following:
(
activity page)
Let Σ be an alphabet. Here's the Mystery Algorithm:
Mystery Algorithm I
Input: alphabet Σ and w ∈ Σ*,
where w = a1a2...an
Output: DFA M such that
... <it's a mystery!>
\[
\begin{array}{l}
M =
\left(\{0,1,\ldots,n+1\},\Sigma,\delta,1,\{n+1\}\right)\text{, where}\\
\delta:\{0,1,\ldots,n+1\} \times \Sigma \rightarrow \{0,1,\ldots,n+1\}\\
\delta(k,x) = \left\{
\begin{array}{cl}
k + 1 & \text{if $0 \lt k \leq n$ and $x = a_k$}\\
0 & \text{otherwise}
\end{array}
\right.
\end{array}
\]
-
Run Mystery Algorithm I on input $\Sigma = \{b,c\}$ and
$w = cbb$. What is the 5-tuple it produces?
-
Take the 5-tuple from the previous step and translate it into a
diagram for the machine. What is the language it
accepts, and how does that language relate to the inputs
$\Sigma = \{b,c\}$ and $w = cbb$?
-
What does the Mystery Algorithm I do? I don't mean what
does it do for the example inputs I just gave you. What I mean is,
"for any alphabet $\Sigma$ and string $w$ over $\Sigma$,
Mystery Algorithm I produces a machine $M$ such that
$L(M) = $..." $\leftarrow$ you complete this sentence!
- What machine Mystery Algorithm I give for $\Sigma=\{a,b,c\}$,
$w = \lambda$?
Does it still "work"?
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!
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 mystery algorithms. Let's rename the Mystery
Algorithm OneString(Σ,w) and refer to the
union algorithm from the previous homework as
Union(M1,M2).
For any finite set of strings
$S = \{w_1, w_2, ..., w_n\} \subseteq \Sigma^*$
there is a DFA accepting $S$.
The following algorithm constructs a DFA
accepting
S, thus proving the theorem:
Algorithm SetStrings
Input: alphabet $\Sigma$, finite set of strings
$S = \{w_1, w_2, \ldots, w_n\} \subseteq \Sigma^*$
Output: machine $M$ such that $L(M) = S$, where
$M = \left(\{0\},\Sigma,\delta(k,x) = 0,0,\{\ \}\right)$
if
$S = \{\ \}$
$M = \text{Union}(
\text{OneString}(\Sigma,w_1),\text{SetStrings}(\Sigma,S - \{w_1\})
)$
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!