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?