Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Consider the following "mystery algorithm":

**Mystery Algorithm II**

**Input:** DFA *M = (Q,Σ,δ,s,W)*
and a character *x ∈ Σ*

**Output:** DFA *M'* such that
... <it's a mystery!>

\[
\begin{array}{l}
M' = \left( Q \cup \{\$,\#\},\Sigma,\delta',\$,W\right)\text{, where}\\
\delta:(Q \cup \{\$,\#\}) \times \Sigma \rightarrow Q \cup
\{\$,\#\}\\
\delta'(q,y) = \left\{
\begin{array}{cl}
s&\text{if $q = \$$ and $y = x$}\\
\#&\text{if $q = \$$ and $y \neq x$}\\
\#&\text{if $q = \#$}\\
\delta(q,y)&\text{otherwise}\\
\end{array}
\right.
\end{array}
\]
**Note:** This is assuming that *$* and *#*
are not already states in the machine. In fact, any two new
states would do, whatever their names. They just need to be new!

## Problem 1

Write down the 5-tuple this algorithm produces on input
character

*x = b* and machine

M = |
( |
{q0,q1},{a,b}, |
| a b
--+-------
q0| q1 q1
q1| q0 q0 |
,q0,{q0} |
) |

## Problem 2

Draw the diagram of the machine from the 5-tuple
produced by the algorithm for the previous question.

## Problem 3

Give a conscise english description of what this algorithm
does. E.g. "

*Given any input character x and any machine M the
algorithm produces a machine M' that accepts ...*"
You fill in the blank!

**Hint:** It might help if you
try to come up with a concise english description of what
the example input machine

*M* does, as well as the
machine

*M'* produced by the algorithm for the example.

## Problem 4

What new properties of languages
accepted by finite automata that can be proved by this algorithm?