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?