\documentstyle[6.045-ps,12pt]{article}

\name{Marc Horowitz}
\psnum{$6^{\prime}$}
\duedate{Friday, March 22}
\section{Bronwyn Eliot, Thursday 1pm}
\handoutnum{??}

\def\Kdfa{\mbox{$K_{\mbox{\tiny DFA}}$}}
\parskip=0.1in

\begin{document}

\problem{1}{Limiting the Number of States}

Generate a Turing machine as follows:

Take the desired regular expression and generate the equivalent DFA.
Now, number all of its states.  Call the set of numbers \Kdfa.  Set
$\Sigma_{\mbox{\tiny TM}} = \Sigma_{\mbox{\tiny DFA}} \times (\Kdfa
\cup \#) \times (\Kdfa \cup \#)$.  The first part of the symbol is a symbol
from the RE's alphabet.  The second part is an optional {\em state
number}, and the third part is an optional {\em temporary number}.

The Turing machine operates as follows.  Rather than giving a rigorous
table of $\delta$ values, I am listing each step in English.  Each
step is either directly translatable to a single TM operation
involving a single state, or has been shown to be doable in a finite
number of states.

\begin{enumerate}
\item Move left to the first character of the input string.

\item Set the state number to the number of $s_{\mbox{\tiny DFA}}$,
goto state \ref{dfa}.

\item\label{dfa}
$\langle$DFA~symbol,DFA~state,empty~temporary$\rangle$ translates to
\hfil\penalty-5000\hfilneg
$\langle$DFA~symbol,DFA~state,DFA~next~state$\rangle$.  If the input
string is empty, go to state \ref{done}.

\item Copy temporary number to the next tape position's state number.
This can be done as follows.

\begin{enumerate}
\item\label{copy} If the last digit of the temporary is 0, remove the
zero and go to state \ref{zero}.  If the last digit is 1, remove the
one and go to state \ref{one}.  If there are no more digits, we are
done.  Move right and go to state \ref{dfa}.

\item\label{zero} Move to the right, go to state \ref{appendzero}.

\item\label{appendzero} Append a zero to the state number and go to
state \ref{left}.

\item\label{one} Move to the right, go to state \ref{appendone}.

\item\label{appendone} Append a one to the state number and go to
state \ref{left}. 

\item\label{left} Move to the left, and go to state \ref{copy}.
\end{enumerate}

\item\label{done} If the current state number is a final state, then
accept the input.  Otherwise, reject it.

\end{enumerate}

This algorithm yields a Turing machine with about $k=10$ states.  More
may be needed depending what is done with an accepting or rejecting
state.  But this is a general algorithm, which requires the same
number of states, regardless of the complexity of the regular
expression.

\end{document}
