\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor,multicol}
\usepackage{varwidth, hyperref}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Homework 7}
\duedate{Due: Saturday June 3, 2017}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
Upload a {\bf single file} to Gradescope for each group.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
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. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. \\
{\sc Reading} Sipser Sections 4.1, 4.2, 5.1, 5.2
\newline
{\sc Key Concepts} Decidable problems, undecidability, uncountability, diagonalization,
reduction.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\vspace{-20pt}
\problemlist{}
\begin{problem}[1.] ({\bf 9 points}) {\bf True / False}. Briefly justify your answer for
each statement.
\begin{itemize}
\item[a.] Any subset of a decidable set is recognizable.
\item[b.] Any subset of an uncountable set is countable.
\item[c.] Any superset of an undecidable set is uncountable.
\item[d.] There is a language that is both countable and undecidable.
\item[e.] There is a decidable but not recognizable language.
\item[f.] The complement of a recognizable language must be recognizable.
\item[g.] Every language reduces to itself.
\item[h.] Every language reduces to its complement.
\item[i.] For any two languages $L_1, L_2$, if $L_1$ reduces to $L_2$
then $L_2$ reduces to $L_1$.
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Prove that the language
\[
\{ \langle R, S \rangle ~|~\text{$R$ and $S$ are regular expressions and
$L(R) \cap L(S) \neq \emptyset$} \}
\]
is decidable.
\end{problem}
\begin{problem}[3.] ({\bf 16 points})
Let $S_{n} = \{\langle M \rangle \st \text{$M$ is a TM and $|L(M)|=n$}\}$
for $n=0,1,2,3, \ldots $
\begin{itemize}
\item[a.] Show that for every $n \geq 0$, $S_{n}$ reduces to $S_{n+1}$.
\item[b.] Show that for every $n \geq 1$, $S_{n+1}$ reduces to $S_{n}$.
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 2 points})
Your feedback about your experience in this course can be extremely valuable.
Please take a few minutes to thoughtfully fill out CAPEs, TA/Tutor evaluations, and
this end of course survey:
\begin{center}
\url{https://goo.gl/forms/U3LG7fQ6Gsf0rKK62}
\end{center}
This HW will be graded out of 35 points so the 2 points for this question are {\bf bonus.}
\end{problem}
\end{document}