ACTIVITY: Mystery Algorithm I
Break up into groups of three, find a whiteboard, and do the following:
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"?