\documentclass{article}
\usepackage{fullpage}
\usepackage{times}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{enumerate}
\usepackage[usenames]{color} 
\usepackage[pst-pdf=md5]{gastex}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\mfr}[1]{\mathfrak{#1}}
\newcommand{\mcal}[1]{\mathcal{#1}}
\newcommand{\pow}[1]{\mathcal{P}(#1)}

\newcommand{\ignore}[1]{}
\newcommand{\mybox}{\fbox}

\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\vpi}{\varphi}
\newcommand{\scl}[1]{{#1}^{\star}}
\newcommand{\ab}{\{a,b\}^{\star}}
\newcommand{\abc}{\{a,b,c\}^{\star}}
\newcommand{\abcd}{\{a,b,c,d\}^{\star}}
\newcommand{\zo}{\{0,1\}}
\newcommand{\sstar}{\Sigma^{\star}}

\newcommand{\derive}{\Rightarrow}
\newcommand{\dstar}{\stackrel*\Rightarrow}
\newcommand{\yield}{\vdash}

\newcommand{\bfa}{\mathbf{a}}

\DeclareMathOperator{\start}{s}
\DeclareMathOperator{\mvleft}{L}
\DeclareMathOperator{\mvright}{R}
\DeclareMathOperator{\blank}{\Box}
\DeclareMathOperator{\halt}{\mathit{h}}
%\newcommand{\blank}{\blacksquare}
\newcommand{\dir}{\{\mvleft,\mvright\}}
\newcommand{\avg}[1]{\langle #1 \rangle}

\DeclareMathOperator{\ecl}{\epsilon\mbox{-CLOSURE}}
\DeclareMathOperator{\Inc}{INC}
\DeclareMathOperator{\Dec}{DEC}
\newcommand{\Lefty}{\mbox{\sc LeftShifter}}
\newcommand{\Leftie}{\mbox{\sc LeftShifter}_{2}}
\newcommand{\Halt}{\mathsf{HALT}}
\newcommand{\Empty}{\mathsf{EMPTY}}




\begin{document}

\par\noindent{\bf CS81 HW\#10 Spring 2012} {\em Out: 04/12/2012. Due: 04/18/2012 (before class)}
\paragraph{Policy on homeworks}
\begin{itemize}
\item {\em Collaboration}:
        You may discuss a question with any other student currently taking CS81 provided:
        (i) both of you contribute equally;
        (ii) you come away from any discussion with an understanding in your mind (and no archived solution of any form is retained);
        (iii) your submission is your own work prepared by yourself on a separate occassion.

\item {\em Reference materials}:
        You should only refer to materials from this semester of CS81
        (class notes, handouts, textbooks, grutors, instructor, etc).

\item {\em Submission}:
        Your submission should be legible or is prepared using TeX.
\end{itemize}

\paragraph{Turing Machines}
Recall our conventions regarding Turing machines:
\begin{itemize}
\item The tape is {\em one-way infinite}. The machine hangs if the tape reader attempts to move
	left off the leftmost tape square.
\item There is a single halt state $\halt$.
\item If a Turing machine $M$ computes a function $f$, then
	$(s,\blank\alpha\underline{\blank}) \yield_{M}^{\star} (\halt,\blank f(\alpha)\underline{\blank})$.
\end{itemize}
\begin{enumerate}
\item Consider the following Turing machine (which we call $\Lefty$).
	\begin{enumerate}
	\item (True or False) $\Lefty$ removes the leftmost blank on its tape; 
		that is, it transforms its tape from $\blank\alpha\underline{\blank}$ to $\alpha\underline{\blank}$.
		If True, describe in English how this Turing machine works; if False, describe a way to fix and
		remove the bugs.
\begin{figure}[h]
  \begin{center}
    \unitlength=4pt
    \begin{gpicture}(60,30)(0,0)
    %\put(-5,0){\framebox(65,45){}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=0}
    %\gasset{Nframe=n,Nadjust=w,Nh=6,Nmr=0}
    \thinlines
    \node[Nmarks=i,iangle=180](S)(0,20){$s$}
    \node(Q1)(15,20){$1$}
    \node(A)(30,30){$a$}
    \node(B)(30,10){$b$}
    \node(X)(45,20){$2$}
    \node(D2)(45,5){$3$}
    \node(H)(15,5){$\halt$}
    \drawloop[loopangle=90](A){$a,a,\mvleft$}
    \drawloop[loopangle=270](B){$b,b,\mvleft$}
    \drawloop[loopangle=0](X){$a/b,a/b,\mvright$}
    \drawedge[curvedepth=0,ELside=l](S,Q1){$\blank,\blank,\mvleft$}
    \drawedge[curvedepth=0,ELside=l](Q1,A){$a,\blank,\mvleft$}
    \drawedge[curvedepth=0,ELside=r](Q1,B){$b,\blank,\mvleft$}
    \drawedge[curvedepth=0,ELside=l](A,X){$\blank,a,\mvright$}
    \drawedge[curvedepth=0,ELside=r](B,X){$\blank,b,\mvright$}
    \drawedge[curvedepth=+3,ELside=l](A,B){$b,a,\mvleft$}
    \drawedge[curvedepth=+3,ELside=l](B,A){$a,b,\mvleft$}
    \drawedge[curvedepth=0,ELside=r](Q1,H){$\blank,\blank,\mvright$}
    \drawedge[curvedepth=0,ELside=l](X,D2){$\blank,\blank,\mvright$}
    \drawedge[curvedepth=+8,ELside=l](D2,H){$\blank,\blank,\mvleft$}
    \end{gpicture}
  \end{center}
\caption{A Turing machine called $\Lefty$.}
\end{figure}

	\item Can you find a smaller Turing machine that makes its leftmost blank disappear?
	\item (True or False) $\Lefty$ will also work if there is more than one blank to the
		left of $\alpha$. If True, explain why; if not, determine if there is a way to fix 
		this so that the leftmost (and only the leftmost) blank is removed.

	\end{enumerate}


\item Describe a Turing machine $M$ that concatenates two strings $\alpha$ and $\beta$:
	\[ 
		(s,\blank\alpha\blank\beta\underline{\blank}) \yield_{M}^{\star} 
		(\halt,\blank\alpha\beta\underline{\blank})
	\]

\item Describe a Turing machine $M$ that computes unary addition over the alphabet $\Sigma = \{0\}$.

\end{enumerate}


\paragraph{Computability}
For each of the following languages over $\Sigma$, state whether the language 
is decidable, semi-decidable, or not even semi-decidable. Justify your answers.
We assume a suitable encoding $\avg{M}$ for each of the models.
\begin{enumerate}
\item $L = \{\avg{M} : \mbox{$M$ is a DFA where $L(M) = \Sigma^{\star}$}\}$
\item $L = \{\avg{M} : \mbox{$M$ is a CFG where $\epsilon \not\in L(M)$}\}$
\item $L = \{\avg{M} : \mbox{$M$ is a DTM where $L(M) = \emptyset$}\}$
\end{enumerate}


\end{document}

