\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth, multicol}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\blank}{\textvisiblespace}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Group Homework 5}
\duedate{Due: Saturday February 24, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
{\bf One member} of the group should upload your group submission to Gradescope.
During the submission process, they will be prompted to add the names of the rest
of the group members.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
Your homework must be typed. Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning.\\
{\sc Reading} Sipser Sections 3.1, 3.2
\newline
{\sc Key Concepts} Formal definitions of Turing machines, computations of Turing machines,
halting computations, implementation-level descriptions of Turing machines, recognizable languages, decidable languages.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]{\bf (10 points)} In class and in the textbook (pages 166-167,
page 173), we
saw a Turing machine deciding the set $B = \{ w \# w \st w \in \{0,1\}^* \}$. In this
question, you will modify this machine so that it decides the set
\[
A = \{ w \# w^\mathcal{R} \st w \in \{0,1\}^* \}
\]
instead.
\begin{itemize}
\item[a)]
Give an implementation-level description of your machine. {\it Follow the
style and conventions demonstrated on page 167.}
\item[b)]
Prove that the machine you gave in part (a) {\bf decides} $A$ by showing that
for any string $w \in \{0,1, \#\}^*$,
\begin{itemize}
\item if $w \in A$, then your machine accepts on input $w$, and
\item if $w \notin A$, then your machine rejects on input $w$.
\end{itemize}
\item[c)]
Draw the state diagram formalizing the machine you described in part (a).
{\it You may use the abbreviations used on page 173 and on this week's Individual
Homework: omit all outgoing transitions for the accept and reject states, and
omit all incoming transitions to the reject state.}
\end{itemize}
\end{problem}
\begin{problem}[2.] {\bf (10 points)} Consider the function from $\{0,1\}$ to
$\{a,b\}$ given by $h(0) = b$, $h(1) = a$.
We can extend $h$ to operate on strings by defining
$h(w) = h(w_1) h(w_2) \cdots h(w_n)$ where $w = w_1 \cdots w_n$ and
each $w_i \in \{0,1\}$.
For example, $h(010) = bab$. Extending $h$ to languages over
$\{0,1\}$, we define $h(L) = \{ h(w) \st w\in L\}$ for any $L\subseteq \{0,1\}^*$.\\
Devise a general construction that, given a Turing machine $M$
over the alphabet $\{0,1\}$, builds a Turing machine $M'$
over the alphabet $\{a,b\}$ that recognizes
$h(L(M))$.\\
A full proof would have three stages: setup, construction, and proof of correctness.
In this exercise you will focus on the setup and construction, and then apply your
construction to an example.
\begin{itemize}
\item[(a)]
\begin{description}
\item[Setup] Consider an arbitrary Turing machine
$M = (Q, \{0,1\}, \Gamma, \delta, q_0, q_{acc}, q_{rej})$, where
$\{0,1, \blank\} \subseteq \Gamma$ and $\{q_0, q_{acc}, q_{rej}\} \subseteq Q$
and $q_{acc} \neq q_{rej}$.
Let $L = L(M)$.
\item[Construction] Build a new Turing machine whose language is $h(L)$.
Specify this Turing machine formally, specifying each component of the
7-tuple formal definition.
{\it You must supply this construction.}
\end{description}
\item[(b)]
\begin{description}
\item[Application] Consider the language, $L$, recognized by this Turing machine:
\begin{center}
\includegraphics[width=3in]{hw5TM.png}
\end{center}
Describe $L$ mathematically (e.g.\ in set builder notation), and briefly justify your
description.
Then, apply your construction from part (a) to this Turing machine and confirm that the
language recognized by the resulting Turing machine is $h(L)$ by describing
its computations.
{\it Include the state diagram of the resulting machine as exported from JFLAP and your justifications in your homework
submission. }
\end{description}
\end{itemize}
\end{problem}
\begin{problem}[3.] {\bf (10 points)} True or False (and justify).
\begin{itemize}
\item[a)]
For each Turing machine $M$, there is some Turing machine $M_1$ with $L(M) = L(M_1)$
and such that $M_1$ never loops (i.e.\ its computations must accept or reject).
\item[b)]
For each Turing machine $M$, there is some Turing machine $M_2$ with $L(M) = L(M_2)$
and such that $M_2$ never rejects (i.e.\ its computations must accept or loop).
\item[c)]
For each Turing machine $M$, there is some Turing machine $M_3$ with $L(M) = L(M_3)$
and such that $M_3$ never accepts (i.e.\ its computations must reject or loop).
\end{itemize}
\end{problem}
\end{document}