\documentclass[12pt]{article}
\usepackage{amsfonts, amssymb, amsmath, comment}
\usepackage[usenames,dvipsnames]{color}
\usepackage[pdftex]{graphicx}
\usepackage{listings}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{url}
\usepackage{xypic}
\usepackage{epsf}
\usepackage{epsfig}
\usepackage{enumitem}

\setlist[itemize]{nosep}
\setlist[enumerate]{nosep}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0in}
\parskip12pt
\parindent0pt
\pagestyle{fancy}
\lhead{CS 360 - Winter 2022}
\chead{CM A06}
\rhead{Due Tues, April 5, 11:59 PM\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2022}

\newcommand{\rmp}{\reversemarginpar\marginpar}

\providecommand{\SolutionQuestionQueueAutomaton}{}
\providecommand{\SolutionQuestionReductionsPartA}{}
\providecommand{\SolutionQuestionReductionsPartB}{}
\providecommand{\SolutionQuestionAnUndecidableLanguagePartA}{}
\providecommand{\SolutionQuestionAnUndecidableLanguagePartB}{}

\input xy
\xyoption{all}

\newtheorem{DefinitionPlaceHolder}{Definition}
\newtheorem{TheoremContextFreeLanguagesAreRecursive}[DefinitionPlaceHolder]{Theorem}

\begin{document}

\begin{itemize}
\item{
Start as early as possible, and contact the instructor if you get stuck.
}
\item{
See the course outline for details about the course's marking policy and rules on collaboration.  
}
\item{
Submit your completed solutions to \textbf{Crowdmark}.
}
\end{itemize}

\begin{enumerate}

\item \label{QuestionQueueAutomaton}
A queue automaton\\
Let $\Sigma $ \rmp{[8]}be an alphabet, which is the alphabet for the languages of all the machines in this problem.
A {\bf queue automaton}, $A$, is like a pushdown automaton which accepts by final state, except that the stack is replaced by a queue.
A {\bf queue} is a tape allowing symbols to be written only to the left-hand end and read only from the right-hand end.
Each write operation (we will call it a {\bf push}) adds zero or more symbols to the left-hand end of the queue and each read operation (we will call it a {\bf pull}) reads and removes one symbol from the right-hand end.
As with a PDA, the input is placed on a separate read-only input tape, and the head on the input tape can move only from left to right.
The input tape contains a cell with a blank symbol following the input, so that the end of the input can be detected.
The queue is empty at the start of execution.
Analogously to the case of a PDA, the transition function for a queue automaton is a function of the current state, the current input symbol (an alphabet symbol or $\varepsilon $) and the symbol currently being pulled from the queue.
Each transition determines a new state, and pushes zero or more symbols onto the queue.
In detail, if the states of $A$ are $Q$, the alphabet for $A$ is $\Sigma $ and the queue alphabet of $A$ is $\Gamma $, then the transition function, $\delta _{A}$, for $A$ is a function
\begin{displaymath}
\delta _{A} : Q \times \left ( \Sigma \cup \{ \varepsilon \} \right ) \times \Gamma \rightarrow Q \times \Gamma ^{*}.
\end{displaymath}
A queue automaton accepts its input by entering a final state at any time.

\noindent
Prove that every recursively enumerable language can be recognized by a queue automaton.
\SolutionQuestionQueueAutomaton

\newpage

\item{ \label{QuestionReductions}
Reductions\\
Let $\Sigma = \{ 0, 1 \}$.
\begin{enumerate}
\item \label{QuestionReductionsPartA}
Let \rmp{[4]}$L$ be a language over $\Sigma $ such that $L \neq \emptyset $ and $L \neq \Sigma ^{*}$.
Let $L_{R}$ be {\bf any} recursive language over $\Sigma $.
Prove that membership in $L_{R}$ can be reduced to membership in $L$.
\SolutionQuestionReductionsPartA

\newpage

\item \label{QuestionReductionsPartB}
Let \rmp{[4]}$L_{RE}$ be a recursively enumerable language over $\Sigma $.
Let $L_{u}$ be the {\bf universal language} as defined in the lecture slides.
(In detail, $L_{u}$ is the set of pairs $(e, w)$ such $e$ is the identifier of a Turing machine, $M$, which accepts the input word $w$.)
Prove that membership in $L_{RE}$ can be reduced to membership in $L_{u}$.
\SolutionQuestionReductionsPartB
\end{enumerate}
}

\newpage

\item{ \label{QuestionAnUndecidableLanguage}
An undecidable language\\
Let $\Sigma = \{ 0, 1 \}$.
\begin{enumerate}
\item \label{QuestionAnUndecidableLanguagePartA}
Give \rmp{[4]}an explicit reduction from membership in the language $L_{\varepsilon +} = \{M \ | \ \varepsilon \in L(M)\}$ to membership in the language $L_{\varepsilon } = \{M \ | \ \{\varepsilon\} = L(M)\}$.
\SolutionQuestionAnUndecidableLanguagePartA

\newpage

\item \label{QuestionAnUndecidableLanguagePartB}
Prove that \rmp{[4]}membership in the language $L_{\varepsilon +}$ from part \ref{QuestionAnUndecidableLanguagePartA} is undecidable.
Do {\bf not} use Rice's theorem.
\SolutionQuestionAnUndecidableLanguagePartB
\end{enumerate}
}

\end{enumerate}

\end{document}