\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{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Group Homework 6}
\duedate{Due: Saturday June 2, 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. We recommend that you submit early drafts to Gradescope so that in
case of any technical difficulties, at least some of your work is present. You may update
your submission as many times as you'd like up to the deadline.\\
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.2, 3.3, 4.1
\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, decidable computational problems.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 10 points}) Find examples of languages satisfying each of the following properties
(and briefly justify), or prove that no such language exists.
\begin{itemize}
\item[a.] An infinite recognizable language that is undecidable and whose complement is finite.
\item[b.] A non-context free language that is undecidable.
\item[c.] A decidable language with an undecidable subset.
\item[d.] A language all of whose subsets are recognizable.
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points})
\begin{itemize}
\item[a.] Given a Turing machine $M$, define (using a high-level description) an enumerator $E$ such that
\[
L(E) = \{ w \st w \in L(M) \text{ and } w^\mathcal{R} \in L(M) \}
\]
{\it You do not need to include a formal proof of correctness, but briefly justify the idea of your construction.}
\item[b.] Given an enumerator $E$, define (using a high-level description) a Turing machine $M$ such that
\[
L(M) = \{ w \st w \in L(E) \text{ and } w^\mathcal{R} \in L(E) \}
\]
{\it You do not need to include a formal proof of correctness, but briefly justify the idea of your construction.}
\item[c.] Referring to your construction in part b, is $M$ a decider? Why or why not?
\end{itemize}
{\it You do not need to include a formal proof of correctness, but briefly justify the idea of your construction.}
\end{problem}
\begin{problem}[3.] ({\bf 10 points})
\begin{itemize}
\item[a.] Let $\Sigma = \{ 0,1\}$. Prove that
\[
\{ \langle A \rangle \st \text{$A$ is a DFA over $\Sigma$ and } L(A) \subseteq L (0^*1^*) \}
\]
is decidable.
\item[b.] Recall that
\[
INF_{DFA} = \{ \langle A \rangle \st \text{$A$ is a DFA over $\Sigma$, $L(A)$ is (countably) infinite} \}
\]
Prove that $INF_{DFA}$ is decidable. {\it Hint: you might find ideas from the Pumping Lemma useful.}
\end{itemize}
\end{problem}
\end{document}